New answers tagged np
0
Intuitively $A \le_p B$ means that a polynomial-time algorithm for $B$ can be used to solve $A$ in polynomial-time, not vice-versa.
That said $f$ is not required to be surjective, think for example of $A=\Sigma^*$ and $B=\{0,1\}$. Suppose that $f(x) = 0$ (i.e., $f$ is the constant function). Simulate the algorithm with $y=1$ and notice that it will reject ...
1
We start with the assumption that there is a non-trivial language $A$ which is in $\mathrm{coNP}$, but not $\mathrm{coNP}$-complete. We note that it is rather straight-forward to see that if $\mathrm{P} = \mathrm{coNP}$, then every non-trivial language in $\mathrm{coNP}$ is $\mathrm{coNP}$-complete. Conversely, Ladner's theorem states that if $\mathrm{P} \...
2
Alright, we are given a language $C \in \mathrm{P}$ and a language $A \in \mathrm{NP}$, and we are promised that $C \leq_p A$. What can we conclude?
First a side remark: The reduction $C \leq_p A$ tells us very little since we know $C \in \mathrm{P}$. The only extra information we get is that if $A$ is empty, then so is $C$, and if $A = \Sigma^*$, then $C = \...
2
Option 1 is odd. We don't know whether a polynomial algorithm can be constructed. The "passing all the neighbors at a distance of less than 6 from each vertex in $G$" is unclear. Any algorithm solving the TSP problem must visit all vertices. Therefore it must also visit all neighbors of each vertex and, in particular, all neighbors at distance less ...
2
1 is wrong. The problem is NP-Complete by an easy reduction $f$ from the clique problem.
Let $\langle G,k \rangle$ with $G=(V,E)$ be an instance of (the decision version of) clique. If $k$ is odd then the reduction is the identity function, i.e., $f(\langle G,k \rangle)=\langle G,k \rangle$. Otherwise create a new graph $G=(V', E')$ with $V' = V \cup \{v\}$...
1
Saying that a "language reaches the state of reject" is meaningless. Languages don't have states. Turing machines and automatons do.
That said, your language is undecidable. Given $\langle M,w \rangle$ you can compute the pair $\langle M',w \rangle$ where $M'$ behaves exactly as $M$ except for the following: every transition that halts the machine ...
2
From what I understand in the question, there is a language that accepts Turing machines that go into an endless loop.
We do not say a language "accepts" something. Rather the language contains all pairs of turing machines and words, where the TM runs forever (which I take "infinite loop" to mean) on the word.
Also, note that you can ...
0
Let $X = \{ x_1, x_2, \dots, x_n \}$ be the (multi-)set of elements in your subset-sum instance and let $t$ be the target value.
Create the undirected graph $G=(V,E)$ where $V=\{a,b\} \cup X$ and $E = ( \{a,b\} \times X) \cup \{(a,b)\}$.
The weight of edge $(a, x_i)$, for $x_i \in X$, is $x_i$. The weight of edge $(b, z)$ for $z \in \{a\} \cup X$ is $0$. ...
1
The main "key" here is to understand how a formula is structured. Assuming the formulas of TAUTOLOGY are in CNF, then there exists a polynomial algorithm:
Let $\varphi=\bigwedge_{i=1}^{k}\limits C_i$ where each $C_i$ is described as an $\lor$ of multiple literals.
Notice, that in order for an assignment $\rho$ to satisfy $\varphi$, we need $\rho$ ...
2
If $\mathrm{FPT}=W[1]$, then we will not directly get an answer to $\mathrm{P}$ vs. $\mathrm{NP}$ (or at least, not that we know). The assumption that $\mathrm{FPT} \neq W[1]$ is a weaker claim than $\mathrm{P}\neq \mathrm{NP}$:
If $\mathrm{P} = \mathrm{NP}$, then there is polynomial time algorithm for the $W[1]$-complete problem $k$-Clique, so $\mathrm{FPT}=...
2
Because $k$-CLIQUE is W[1]-hard, your result would imply that FPT = W[1], which by the result of Downey and Fellows [1] implies that the Exponential Time Hypothesis (ETH) is false, i.e., that 3-SAT can be solved in $2^{o(n)}$ time. But ETH is stronger than P not equal to NP, so its falsification doesn't settle P = NP (but of course, if true, ETH would imply ...
0
$P$ is closed under complement. The rest is up to you.
0
It is 2 that is correct. Here is an alternative explanation:
Notice that any language in $P$ has to be $P$-complete. In addition to that, if $P=NP$ then $NPC=P$-complete. Combining both arguments implies that $NP=P=P\text{-complete}=NPC$. Therefore, if $NP\neq NPC$ then $P\neq NP$.
1
I assume that by "verses" you mean boolean formulas.
The language is definitely in CO-NP since a "no" certificate is a satisfying assignment.
Currently we don't know whether FALSE is in P nor whether it is in NP.
1
A clique $C$ on $k$ vertices has $\binom{k}{2}$ edges, i.e., all unordered pairs $\{a,b\}$ such that $a$ and $b$ are distinct vertices in $C$.
The number of such pairs is $\frac{k (k-1)}{2} = \binom{k}{2}$. You can count these by focusing on the number of ordered pairs first.
To make an ordered pair $(a,b)$ you have $k$ choices for $a$ and $k-1$ choice for $...
1
$L$ is given as part of the input, and can be e.g., $n/2$, where $n$ is the number of items.
Then, iterating over ${n\choose L}={n\choose \frac{n}2}$ is exponential.
Note that it doesn't matter whether $L$ is given in unary or binary, since $n$ is given in unary (as a list of the different items).
1
Theorem. Any finite language L is in P.
Proof.
Let M be a Turing machine which has all strings of L on its tape. When given an input it checks whether the input is on its tape. This is O(1) time clearly.
Theorem. If and only if P=NP, then every L in P (including thus all finite languages) are NP-Complete.
Proof.
Recall that a language is NP-Complete iff ...
1
You are right that that doesn't prove the algorithm is polynomial, as it just gives the certificate. But it is very easy to see that (for example with a program in a C-like language, given a reasonable representation of the graphs) the check is very easy to do (is polynomial).
The part of coming up with a polynomial verifier given a reasonable certificate (...
2
The second approach is technically the correct interperation. When we say "a verifier gets a certificate $c$ that looks like [...] and computes something", then we actually mean that this verifier checks whether $c$ is of the required format (e.g, check that $c$ is representing a subset of nodes from the graph), and if it isn't it will immediately ...
Top 50 recent answers are included
