|
|
Close Help | ||||||||||||||
Flowshop scheduling deals with processing a set of jobs through a set of machines, where all jobs have to pass among machines in the same order. In this talk we concentrate on a special case of flowshop defined by additional machine dominance constraints. We build up on works by Adiri and Pohoryles [1] and by Ho and Gupta [2]. First of all we prove that the algorithms presented in [1,2] which generate the best permutation schedules for certain objective functions in fact generate optimal schedules. This is achieved by showing, that the set of permutation schedules is a dominant set for this specially structured flowshop problem. Moreover, we extend this result from the objective functions studied in [1,2] to all regular objective functions. Secondly we show, that for a quite broad class of regular objective functions (which includes all commonly used ones), the studied flowshop problem can be effectively reduced to a single machine problem. This reduction yields a polynomial time optimization algorithm for the studied flowshop problem whenever a polynomial time optimization algorithm for the corresponding single machine problem is known.
Článek ukazuje, že pokud k-SAT vyžaduje exponenciální čas O(2^{s_k n}), pak posloupnost s_k roste s k.
We prove tight lower bounds for the monotone depth of functions in monotoneP.
As a result we achieve the separation of the following classes.
1. monotoneNC and monotoneP.
2. For every i >0, monotoneNC^i and monotoneNC^{i+1}.
Only a separation of monotoneNC^1 from monotoneNC^2 was previously
known.
Our argument is more general: we define a new class of communication
complexity search problems, referred to below as DART games, and we prove
a tight lower bound for the communication complexity of every member of
this class. As a result we get lower bounds for the monotone depth of many
functions.
Dokážeme, že tzv. DLL algoritmy (také zavane Davis-Putnam) pro splňování k-CNF vyžadují čas 2^{n(1-\epsilon_k)}, kde \epsilon_n jde k 0 s k rostoucím do nekonečna.
We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within any constant factor. These results are very robust in that they hold for almost all natural proof systems.
For several NP-complete problems, there have been a progression of better but still exponential algorithms. In this paper, we address the relative likelihood of sub-exponential algorithms for these problems. We introduce a generalized reduction which we call Sub-Exponential Reduction Family (SERF) that preserves sub-exponential complexity. We show that Circuit-SAT is SERF-complete for all NP-search problems, and that for any fixed $k$, $k$-SAT, $k$-Colorability, $k$-Set Cover, Independent Set, Clique, Vertex Cover, are SERF-complete for the class SNP of search problems expressible by second order existential formulas whose first order part is universal. In particular, sub-exponential complexity for any one of the above problems implies the same for all others.
We also look at the issue of proving strongly exponential lower bounds (that is, bounds of the form $2^{\Omega(n)}$) for AC. This problem is even open for depth-3 circuits. In fact, such a bound for depth-3 circuits with even limited (at most $n^{\epsilon}$) fan-in for bottom-level gates would imply a nonlinear size lower bound for logarithmic depth circuits. We show that with high probability even degree 2 random GF(2) polynomials require strongly exponential size for $\Sigma^k_3 $ circuits for $k=o(\log\log n)$. We thus exhibit a much smaller space of $2^{O(n^2 )}$ functions such that almost every function in this class requires strongly exponential size $\Sigma_3^k$ circuits. As a corollary, we derive a pseudorandom generator (requiring $O(n^2)$ bits of advice) that maps $n$ bits into a larger number of bits so that computing parity on the range is hard for $\Sigma_3^k$ circuits.
Our main technical lemma is an algorithm that, for any fixed $\epsilon>0$, represents an arbitrary $k$-CNF formula as a disjunction of $2^{\epsilon n}$ $k$-CNF formulas that are sparse, e.g., each having $O(n)$ clauses.
This paper gives nearly optimal lower bounds on the minimum degree of Polynomial Calculus refutations of Tseitin's graph tautologies and the mod p counting principles. These are the first bounds for polynomial calculus that distinguish linearly between proofs over fields of characteristic $p$ and $q$, where $p$ and $q$ are distinct primes.
The counting class #P was first defined by Valiant as the class of functions,
which can be computed as the number of accepting computations of a nondeterministic
Turing machine working in polynomial time. Later, other counting classes
#L, #NC^1, #AC^0, etc. were defined. To capture functions which might have
negative values, GapP, GapL, GapAC^0 are considered.
Two definitions of GapAC^0 were proposed: as #AC^0 -#AC^0 (referred
to as DiffAC^0), and as the class of functions computables by arithmetized
AC^0 circuits augmented by the constant -1. It was an open question whether
GapAC^0=DiffAC^0. We will anwser this question positively.
After that, we will consider the question whether #AC^0 and GapAC^0
are closed under division by a constant. It appears that GapAC^0 is closed
under division by a constant m iff m is a power of 2. #AC^0 is not closed
under division by any constant.
and
Matthias Krause (Mannheim, SRN)
On connections between learning and communication complexity
