New answers tagged

1

The accepted answer is incorrect: assuming $P\not=NP$ there are lots of problems incomparable with $SAT$, hence neither $NP$ nor $NP$-hard. Here's an overkill generalization of this fact: Suppose $X\not\in P$. Then there is some $Y$ such that $Y$ is incomparable with $X$ under polynomial-time-Turing reducibility (hence a fortiori Karp reducibility). (So ...


4

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case. If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard. For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this ...


0

Let us take as an example MAX CUT. The optimization problem is: given a graph $G$, find the value of the maximum cut. The decision problem is: given a graph $G$ and an integer $k$, determine whether there is a cut of value at least $k$. If we can solve the optimization problem, then we can solve the decision problem: just compare the value of the maximum ...


2

Concretely, we are always dealing with syntactical transformations, regardless whether there is a semantic theory that renders these transformations intelligible to us, or not. In the end, our ability to automatically demonstrate that two different programs are equivalent is restricted to properties that can be defined syntactically. Even then, there are ...


2

Your problem is decidable. If $M$ always executes less than 5 steps, then it never sees more than the first 4 symbols of its input. Hence it suffices to run $M$ on all inputs of length at most 4.


0

A language is a decision problem. $L \subseteq \{0,1\}^*$, a generic language, is a subset of $\Sigma^*$ (where $\Sigma$ is the alphabet). Decidable languages are by definition countable, as every Turing Machine has a finite description. We can prove that there is no bijective mapping between the set of all turing machines to the set of all subsets of $\...


1

Regarding the specific problem you pose about whether the bit of a number can be permuted to give a prime, I believe the following to be an algorithm in P. If the number has fewer than 100 zeros in it or fewer than 100 ones in it, enumerate all permutations and test them all for primality using a primality test (e.g. AKS) and output accordingly. Otherwise ...


7

The Time Hierarchy Theorem states that for any (reasonable) function $f$, there exists a problem that cannot be solved in time substantially faster than $f(n)$. The proof of this is similar to the proof of the undecidability of the Halting problem: we construct the decision problem "given a description of a Turing machine, does it halt in time at most $f(n)$ ...


1

NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”. So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So ...


0

It's almost always the case that problem sizes are expressed as a function of the length of the input, so a number n would be taken to be $\log n$ in length. For example, your verification would be in poly time if it ran in $O(\log^k n)$ time for some integer $k$.


Top 50 recent answers are included