New answers tagged reductions
3
The problem is NP-hard, at least for a particular simplified configuration.
Assume that each $m_l$ is effectively infinite - we can scan a particular libraries' books all on the day we get access. Let all $d_l = 1$ - each library takes one day to get access to, meaning we get access to exactly $n$ libraries. Now if $P_b = 1$ the thing that maximizes our ...
3
IS there a consensus on the definition of a computer program in CS literature and if so, what is it?
Computer Science is far too diverse to have a single notion of program. For a theoretician, it might be an input tape to a universal Turing Machine, or any lambda expression in lambda calculus. For someone working on the front end of a compiler, it could be defined by a formal grammar while for someone working on the back end, or to the HW architect, it ...
1
IS there a consensus on the definition of a computer program in CS literature and if so, what is it?
This is not IMO a 'computer science' matter. A 'program' is necessarily expressed in a particular programming language, whether that's a programming language with an implementation on a computer, or a 'mere' logical formalism.
The particular language will tell you what a program is. Which means that it's a grubby implementation issue, not a pristine ...
1
Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $W = k$. There is a subset of sum at least $k$ and at most $W$ iff there is a subset of sum exactly $k$.
In the other direction, the idea is to add to the collection a small set of items satisfying the following two ...
1
Search for Bellare and Goldwasser "The Complexity of Decision vs. Search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119, or Bellare's class note on the matter.
0
It is easy to see that if both $L$ and it's complement $\bar{L}$ are recognizable by Turing machine, they can be decided (copy the input to a new tape, then run the machines for $L$ and $\bar{L}$ in parallel, the first one to stop tells you what the answer is; by assumption at least one of them stops in finite time). So the possibilities are:
$L$ and $\bar{...
1
An answer to this precise question is given by Bellare and Goldwasser, "The Complexity of Decision Versus Search", SIAM Journal on Computing, 23:1 (February 1994), DOI /10.1137/S0097539792228289; a more expository version of the above is
Bellare's class note on this. The short answer is that if the decision problem is NP-complete, the search problem is "NP-...
0
A clause in 3-CNF can be converted to k-CNF by adding extra padding:
(l1 V l2 V l3) can be converted to (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y')
Keep adding this extra padding until each clause contains k literals.
Same way, a k-CNF clause can be broken until each clause contains 3 literals.
(l1 V l2 V l3 V l4) can be broken into (l1 V l2 V y) ∧ (l3 V ...
1
The direction of reduction that you are asking for is a bit strange. Typically, we reduce from $A_{TM}$, in order to show undecidability.
Perhaps you meant to ask about the other direction?
At any rate, in answer to your question: your attempt was actually quite close, it just needs a bit of modification. Here's how you can proceed:
Given $M_1,M_2$ as ...
3
Using the proof of the Cook–Levin theorem, for every input $x$ you can construct in polynomial time a SAT instance $\phi(r,z)$ which encodes "$M$ accepts when run on input $x$ and randomness $r$". Here $r$ is a vector of $m = \mathit{poly}(n)$ bits, representing the random bits of $M$, and $z$ is an auxiliary vector, with the following property: in any ...
0
I don't know of a reference, but there's a standard reduction from Hamiltonian paths/cycles to SAT which is fairly well-known. The reduction from SAT to 3SAT is then done by introducing additional variables to break up clauses, e.g.:
$$v_1 \vee \neg v_2 \vee v_3 \vee \neg v_4 \Rightarrow \left( v_1 \vee \neg v_2 \vee X\right) \wedge \left( v_3 \vee \neg v_4 ...
1
The decision problem that corresponds to $L$ deals with the behaviour of Turing machines, not with strings of $1$'s and $0$'s.
More precisely, the decision problem is
Given a Turing machine $M$, is it the case that $L(M) = \{ 1^n0^n \mid
> n \geq 0 \}$
A decider for this decision problem would take as input the description $\langle M \rangle$ of an ...
2
You're using the terminology of recursion theory. Let me rephrase the argument in terms of computer programs.
$K$ is the set of all programs $x$ which halt when run on $x$ as input.
$K_1$ is the set of all programs $x$ which halt on some input.
Given a program $x$, consider the following program $f(x)$:
For $n=1,2,3,\ldots$: run program $x$ on inputs $1,\...
3
I know an example of a problem that is missing two of the four features you ask for - it is not NP-complete, and it is not a problem on graphs.
Buchfuhrer and Umans (2011) show that the minimum equivalent expression problem in Boolean logic is complete for $\Sigma^P_2$ under polynomial-time Turing reductions.
Given a Boolean $(\wedge;\vee;\neg)$-formula $F$...
2
As in the comment, consider the collection of problems $N$-SAT (Is $\phi$, a logical formula in $N$-CNF, satisfiable?). Or $N$-coloring of graphs, for $N \ge 3$ (Can the graph be colored with $N$ colors?). Many NP-complete problems have some parameter (Is there a clique of size $k$ in the graph? Has the digraph a feedback vertex set of size $k$?).
0
For every integer k, take the travelling salesman problem with n > 1 cities where n is a power of k. (Picked the problem that way because all the instances are distinct, so we can say with good conscience that these are distinct problems).
Top 50 recent answers are included
