New answers tagged

0

If one has access to a polynomial algorithm solving $Z$, then there exists a polynomial algorithm for $Z$. That's the main point of reductions for complexity classes. Problem $X$ is at least as hard as problem $Z$. Another point to be made here is that the class $NP$ is about worst-case complexity, i.e. language $X$ can be $NP$-hard because some instances ...


2

You explain how to convert a ZPP machine to a BPP machine. This means that if a problem is in ZPP, then it is also in BPP. In other words, ZPP is contained in BPP.


1

The trick to reducing any NP problem to SAT is 1) writing a subroutine that checks the polynomially-sized certificate, 2) converting that routine to a circuit, and 3) flattening the circuit to CNF using the usual methods. For example, to convert integer factorization to SAT, you would write a routine that multiplies two $n$-bit multipliers producing a 2$n$-...


3

Let us actually prove more: If $L$ is a language and $L \not\in \mathsf{R}$, then $L \not\le_\mathrm{T} L'$ for any $L' \in \mathsf{R}$. (Here, $\le_\mathrm{T}$ indicates a Turing reduction; this is synonymous with your notion of a "computability" reduction.) In other words, $\mathsf{R}$ is closed under Turing reductions. Suppose towards a contradiction ...


0

Usually, there are no intuitive or enlightening reductions between problems in different problem domains. The proof that 3SAT is NP-complete is essentially by writing a formula that says "This NP Turing machine accepts this input." For other problems about logical formulas, you can often translate the formula into a 3SAT instance. Sometimes, you can ...


0

Preparation Since we are talking about the exact number of steps run by a Turing machine (TM), a fixed formal definition of TM is in order. This answer assumes the popular definition of a one-tape Turing machine as in Hopcroft and Ullman (1979, p. 148). Let $N(w) \downarrow$ denote $N$ on $w$ halts eventually. Let $N(w) \uparrow$ denote $N$ on $w$ never ...


0

If you allow arbitrary $e_i$, you are in muddy ground. Are your numbers real? No way to express them finitely, NP-whatever right out the window. Rational? The input size can blow up almost arbitrarily, again nothing relevant to prove. Note that (for very good reasons) NP-hard and its ilk talk about the worst case complexity of the problem (that is well-...


0

It is some sort of necro-answer to already answered and accepted question, but I want to note, that there is really easier way. Consider you have one of inequalities like this: $5*x_1 + 2*x_2 + 3*x_3 \leq 6$ You may easily test all no-vectors for this inequality: $(1, 1, 1)$, $(1, 1, 0)$ and $(1, 0, 1)$ others are ok. First vector $(1, 1, 1)$ means that ...


4

Start with $5|E(G)|$ variables $x_{e,i}$, one for each $e \in E(G)$ and $i \in \{1,2,3,4,5\}$. Intuitively $x_{e,i}$ means that edge $e$ is colored with color $i$. A CNF formula $\phi$ can be obtained by the logical and of the following sub-formulas. Each edge must have exactly one color: At least one color, for each $e \in E(G)$: $(x_{e,1} \vee x_{e,2} \...


2

Is that proof correct? Let's assume f is computable. Then I can show a TM which solves halting problem, actually even more - a TM which prints all halting TMs of given size. This TM works as following: Using blackbox for f, calculate f(n) Iterate through ALL possible TMs of input alphabet {0, 1}, states {0, 1..., n}, work alphabet {_, 0, 1, .... n} ...


0

Suppose a maximum matching, of size r say, is removed from the graph, along with the endpoints of edges of the matching and edges incident to these endpoints. Suppose k vertices remain. These k vertices form an independent set (otherwise the graph would have had a larger matching, a contradiction)and so covering them requires k separate edges. So a minimum ...


1

Here is the reduction from the halting problem, whether a given TM halts on empty input, as given in Yuval's comment. For a TM $M$, let $K$ be the same as $K$ but ignoring inputs. That is, for any input, $K$ will first erase the input so that it looks like an empty input is given. Then $K$ will simulate $M$ on empty input. When the simulation halts, $K$ ...


Top 50 recent answers are included