New answers tagged np
1
$\mathsf{P}^{\mathsf{NP}}$ is the closure of $\mathsf{NP}$ under polynomial time Turing reductions (=Cook reductions). Therefore, it is closed under Cook reductions, so that we have $\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{P}^{\mathsf{NP}}}$. In fact, for any oracle $\mathsf{A}$, we define $\mathsf{P}^{\mathsf{A}}$ as the closure of $\mathsf{A}$ under ...
3
The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this?
First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has ...
1
To say $\mathsf{NP}$ contains problems with "small verifiable witnesses" is conceptually inaccurate at best. The witnesses are only polynomially bounded because we want the verifier to be efficient (i.e., run in polynomial time). In such a setting, only a polynomially long prefix of any witness can be relevant, hence why we insist on polynomially long ...
8
There is a logical interpretation of the various levels of the polynomial hierarchy, which extends the witness characterization of $\mathsf{NP}$ and $\mathsf{coNP}$.
A language $L$ is in $\Sigma_k^P$ if there is a polytime predicate $f$ and a polynomial $\ell$ such that
$$
x \in L \Leftrightarrow \exists |y_1| \le \ell(|x|) \; \forall |y_2| \le \ell(|x|) \; ...
5
Before it was proven that primality is in P, it was known that a complete factorisation if n-1 could be used to prove primality of n. Now this also requires a proof that all factors in the claimed factorisation are actually themselves primes; this leads to a O(n^2) size certificate.
Google for “Pratt certificate”.
(When you use a certificate to solve a ...
2
The $\mathsf{PRIMES}$ problem is in $\mathsf{P}$, so it can be decided by a TM in polynomial time. This means that any certificate suffices, in particular even the empty string, since the verifier (which is a poly-time TM) can simply ignore the certificate and check membership directly.
3
If we are assuming that $coNP≠𝑁𝑃$,
we can conclude that every language that is $co
NP$ complete is not in $NP$ (a contradiction to your given assumption).
Thus, every language we already know of that is $coNP$ complete, is complete as well in $coNP -NP$.
1
Suppose language $D \in NP$ and for every input $w \in D$, the certificate $y_w$ is of logarithmic length; $|y_w| = O(\log|w|)$, and a polynomial verifier $V(w,y)$ exists for $D$.
We can also say: a constant $c$ exists s.t for any $w \in D$ whose certificate is $y_w$, $|y_w| \leq c \log |w|$
Consider the following algorithm $A$:
Given input $x$, for every ...
0
Your problem is known as 3-dimensional matching, or 3DM. It is one of the 21 problems proved to be NP-hard in Karp's original paper (number 17 on his list).
0
Let's say that the numbers $a_1,\ldots,a_n$ are non-negative, and sum to $A$. They induce a probability distribution on $\{1,\ldots,n\}$, in which the probability of $i$ is $a_i/A$.
Given a partition $S_1,S_2,S_3,S_4$, let $I$ be a random variable distributed as above, and let $X$ be the index of the set to which $I$ belongs (so $X \in \{1,2,3,4\}$).
Your ...
0
NP-hardness is a category that applies to both decision problems and optimization problems. In contrast, NP-completeness is a category that applies only to decision problems.
Here are the relevant definitions:
A decision problem is in NP if it is accepted by some polynomial time nondeterministic Turing machine.
A decision problem is NP-hard if all problems ...
0
Suppose that there exists an integer $K$ and a polynomial time algorithm $A$ which, when run on a graph $G$, outputs a value $A(G)$ which satisfies
$$
|A(G) - \alpha(G)| \leq K,
$$
where $\alpha(G)$ is the maximum size of an independent set in $G$.
We will show that $A$ can be used to determine $\alpha(G)$ in polynomial time, which contradicts the ...
9
Yes. Here's a sketch of a direct proof.
If a problem is in $\mathrm{NP}$, there is a nondeterministic Turing machine $M$ that decides it, and there's a polynomial $p$ such that none of $M$'s computation paths on inputs of length $n$ take more than $p(n)$ steps. That means that a single path can't use more than $p(n)$ tape cells, so we can ...
27
Generally speaking, the following is true for any algorithm:
Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time.
Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain ...
3
[...] the structure formerly known as the Polynomial Hierarchy collapses to the level above $\text{P}=\text{NP}$.
This claim makes no sense. If $\text{P}=\text{NP}$, then the whole polynomial hierarchy is equal to $\text{P}$ and there is no level above that.
That is, we show that $\text{co-NP}\subseteq\text{NP}\setminus{P}$.
$\text{co-NP}\subseteq\...
4
I believe the claim is more commonly written as $coNP \subseteq NP/poly$, but that of course does not immediately answer your question.
The fact that this implies that the polynomial hierarchy collapses is shown in Theorem 2 here:
Chee-Keng Yap. Some consequences of non-uniform conditions on uniform
classes. Theoretical Computer Science, 26:287–300, 1983....
Top 50 recent answers are included
