New answers tagged reductions
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
