New answers tagged complexity-theory
2
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
1.)
If we look at $n=8$ then we see:
$$\frac{1}{2^4}\times\left((n-6)(n-5)(n-4)(n-3)(n-2)\right)\times \left((n-5)(n-4)(n-3)(n-2)\right)$$
$$=\frac{((n-2)!)^2}{2^5}.$$
Therefore we can formulate $f_n(n)$ as follow:
$$f_n(n)=\frac{n-(n-2)}{2^{n-4}}\times \prod_{i=3}^{n-2}i^2$$
$$=\frac{n-(n-2)}{2^{n-4}}\times \prod_{i=3}^{n-2}i\times \prod_{i=3}^{n-2}i$$
$$=\...
1
Your algorithm $Z$ doesn't decide $A$. If the input is in both $A$ and $B$, then it returns "no" even though the correct answer is "yes." The error can't be fixed, since it's generally impossible to deduce whether an input is in $A$ if you only know its membership status in $B$ and $A \setminus B$.
2
It seems that:
$$
f(n) = \left( 2\prod_{i=3}^{n-2} i^2 \right) \cdot \frac{1}{2^{n-4}}
= \frac{1}{2^{n-5}} \cdot \frac{1}{2^2} \cdot\prod_{i=1}^{n-2}i^2
= \frac{1}{2^{n-3}} \cdot \left( \prod_{i=1}^{n-2}i \right)^2
= 2^{3-n} ((n-2)!)^2.
$$
This time complexity is superexponential. Indeed, using Stirling's approximation:
$$
2^{3-n} ((n-2)!)^2 \sim 2^{3-n} \...
1
Take $B=\Sigma^*$. Obviously, $A\setminus B=\emptyset$ is not NP-complete. I'm not sure how concatenation has anything to do with set subtraction, but obviously, concatenating $B=\Sigma^*$ to $A\setminus B=\emptyset$ won't yield $A$ back, since $\Sigma^* \emptyset=\emptyset$ as $\emptyset$ doesn't contain any words.
1
Let $C$ be any language in $NP \setminus \{ \emptyset \}$. Notice that such a $C$ exists (e.g., $C = \Sigma^*$).
The claim "if $A$ is $NP$-Complete and $B$ is in $P$ then $A \setminus B$ is $NP$-complete" is false (regardless of whether $P=NP$).
To see this pick $B=\Sigma^*$. Then $A \setminus B = \emptyset$.
Since there is no polynomial-time ...
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 ...
2
Let $L\in NP$. Thus, $L\le_p A$. Since $A\in coNP$, then $L\in coNP$. Hence, $NP\subseteq coNP$.
Now, let $L\in coNP$. Thus, $\overline{L} \in NP$ and therefore $\overline{L}\le_p A$. From reduction properties, we know that $L\le_p \overline{A}$ holds as well. Now, since $A\in coNP$ then $\overline{A}\in NP$. Hence, $L\in NP$, and therefore we get that $coNP\...
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 a problem is in $NPH$ then it is also in $NPC$
This statement is incorrect. A language is in $NPC$ if it is in $NPH$ and it is in $NP$.
Answer 4 is incorrect as well since that would imply that any language $L\in NP$ can be reduced to $F$, hence $L\le_p F$ and since $F\in coNP$ then $L\in coNP$. Hence, $NP\subseteq coNP$. Its not hard to show the other ...
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
This question refers to a specific transformation that you have seen during the course but we are not given, so we can only guess.
A standard transformation from a SAT clause $C$ to a collection of 3-SAT clauses is as follows:
If $C$ already contains $3$ literals, then $C$ is left unchanged.
If $C$ contains $1$ (resp. $2$) literals, then add $2$ (resp. $1$) ...
2
We don't know whether this is true.
This is true, a certificate is an edge coloring with at most $k$ colors.
This is true. Edge coloring is a well-known NP-hard problem (see here for a reduction from 3-SAT) and hence there is Karp reduction from every problem in NP to it. In particular there must also be a reduction from vertex coloring (which is NP-hard) ...
1
For (3), you are correct, i.e., the problem is NP-complete. As a side note, you might also like to know that you can solve edge coloring by using vertex coloring algorithms by taking the line graph. Note that this in itself does not prove NP-completeness.
For (2), you need to show that if you given a certificate, then you can verify it in polynomial time. ...
1
Regarding question 1.
The decision version of MMS is NP-hard by a reduction from partition but
it is currently unknown whether it belongs to $\mathsf{P}$, $\mathsf{NP}$, or $\mathsf{CO\!-\!NP}$.
Regarding question 2.
We don't know whether there exists a polynomial-time algorithm for MMS. I'm not aware of an argument that allows to rule out greedy algorithms ...
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.
0
Interesting question.
The sentence is: determining whether a mathematical statement is true or false
1 - There are plenty of mathematical statements which could easily be decided right or wrong as you have depicted using 2*3=6 example. Hence making a general rule using the phrase -a mathematical statement- is startling, since it simply implies "any ...
0
It's important to address the elephant in the room:
Why has it taken so long to prove that P != NP?
This has not been proven.
The argument you have given "does not compute" - it uses terms that simply do not find together.
The one (the question of whether $P$ equals $NP$) and the other (the difficulty of finding a proof for it or its opposite) ...
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).
3
Why does the proof of the time hierarchy theorem relativize? The time hierarchy theorem is proved by diagonalization. Such proofs tend to relativize. In order to know for sure, all you have to do is to repeat the proof of the time hierarchy theorem, when all concerned Turing machines are oracle Turing machines having access to the same oracle. If the proof ...
1
Assuming words cant overlap, we will prove that the statement is false. Lets try to think about $\Sigma^*$ and see what happens (since as you said, it could be used to create a polynomial counter for all other languages in $P$).
Without loss of generality, we can assume that the polynomial counter will contain the words in increasing lexicographical ordering ...
1
The following assumes that words cannot overlap on the output tape.
Let $\Sigma=\{0,1\}$, pick $\Sigma^* \in \mathsf{P}$ as your language and suppose that there is a polynomial counter $T$ for $\Sigma^*$.
Let $p(|w|) = |w|^{c_1} + c_2$ with $c_1, c_2 \ge 0$ be a polynomial for such that a word $w \in L$ starts in position at most $p(|w|)$ on the output tape ...
2
You haven't explained what $|\varphi|$ is, so let's guess that it is the number of clauses. So you are given a CNF $C_1 \land \cdots \land C_n$ in which each clause contains at least $\log_2 n$ distinct literals.
Any clause which contains both a variable and its negation is always satisfied, so we can remove such clauses; call them spurious. Suppose that the ...
2
The claim is false.
Let $\varphi = (x_1 \vee x_2) \wedge (\overline{x}_1 \vee x_2) \wedge (x_1 \vee \overline{x}_2) \wedge (\overline{x}_1 \vee \overline{x}_2)$. Here $|\varphi|=4$, each clause in $\varphi$ contains exactly $\log_2 |\varphi|=2$ distinct literals, yet $\varphi$ is not satisfiable. (This is also a counterexample if $|\varphi|$ denotes the ...
3
The reference you should have found is [1], where the authors consider several parameters and also higher dimensional knapsack problems (see e.g., Table 1 for a list of running times for different parameters). A non-paywalled version is on arXiv.
[1] Gurski, Frank, Carolin Rehs, and Jochen Rethmann. "Knapsack problems: A parameterized point of view.&...
2
Consider the greedy algorithm that iteratively searches for two distinct pairs of intervals that can be merged, merges them, and repeats until no more merges are possible.
We need to show that this algorithm is optimal.
Notice that, at each point in time during the algorithm, we can associate the generic $i$-th pair $\mathcal{I}_i$ with a set $P_i$ ...
3
Sometimes a short and easily verifiable proof takes a long time to discover.
This may be due to several reasons.
Maybe the general consensus in the research community is that the claim is probably not true, and most people who work on it are trying to prove the converse.
Maybe it's believed to be too difficult for current techniques, and most researchers ...
1
Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid then there must exist an algorithm $B$ that decides whether such a short proof exists.
Let's use $B$ on the statement $\mathsf{P}=\mathsf{NP}$.
There are ...
2
There are two ways to go about this.
Firstly, you could try constructing the product automaton M(Q, Σ, δ, q, F), where Q is the cartesian product of the sets A(Q) and B(Q) where, A is an automaton which accepts all strings having 11 as a substring and B accepts all strings having 010 as a substring. A state S(p, q) in M is final if p ∈ A(F) and q ∈ B(F).
...
0
Regarding 1. Consider a CNF-SAT formula $\phi$ with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$.
For $i=1,\dots,n$ define $s_{i,0} = \{ C_j \mid \overline{x}_i \in C_j\}$ and $s_{i,1} = \{ C_j \mid x_i \in C_j\}$.
The formula $\phi$ is satisfiable if and only if it is possible to select one $s^*_i \in \{s_{i,0}, s_{i,1}\}$ for each $i$ ...
0
Here a possible function $f$ that provides the reduction from $L_1$ to $L_2$.
$$
f(x) = \begin{cases}
\varepsilon & \mbox{if $x=a$} \\
b & \mbox{otherwise}
\end{cases}.
$$
4
No, because nondeterministic Turing machines are not "reasonable" in the sense used here. In this context, the ECT talks about realistic models of computation, i.e., models that can be implemented on physical devices. Nondeterminism cannot be implemented directly given our current understanding of physics (we can simulate it on a deterministic ...
3
You are indeed correct that it isn't $n^n$ (though this is good enough for most purposes). As OmG mentioned in the comments, there is a standard approximation formula called "Stirling's approximation formula" which gives the following asymptotic bound:
$$n!=\Theta\Big(\sqrt{n}\frac{n^n}{e^n}\Big)$$
2
Lets say there are $N(n)$ partitions. Then, for each partition you do $O(n^c)$ work (important note: make sure for all partitions this is the same $O(n^c)$. That is, for this particular $c$, for all partitions it takes $O(n^c)$!)
This means that the total work will be $O(n^c)$ times $O(N(n))$ (because you do $O(n^c)$ work for $N(n)$ iterations), hence a ...
3
Your idea is in a good direction. To complete this proof, you will need to note a few things, and explain why they are not problems (or how to fix them):
The new machine will only do one oracle call at the end. That means, that at any time that our original TM did an oracle call, it wont get an answer!
We need to "save up" and "remember"...
0
For $n \ge 16$ you have $k \ge \frac{n}{8} \ge 2$ and you can write the following:
$$
\sum_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) \ge
\frac{n-(k-2)}{k-(k-2)-1}
> n-k \ge n - \frac{n}{8} = \frac{7}{8} \cdot n.
$$
For $2 \le n<16$, $\frac{n}{2 \log_2 n} < \frac{16}{8} = 2$ (notice that $\frac{n}{2 \log n}$ is a monotonically increasing ...
5
To summarize: No, this paper does not provide an example of something a quantum computer can compute that a Turing computer can't.
I believe you have misunderstood Henry's comment. The problem in question isn't the halting problem (given any Turing machine and input, will it halt). Rather, the problem is to prove that a program halts, given that it halts. As ...
4
The standard example is the variant of SAT in which each clause has the form $x$ or $y \oplus z$ (not allowing negations). For more examples, check Allender, Bauland, Immerman, Schnoor and Vollmer, The Complexity of Satisfiability Problems:
Refining Schaefer’s Theorem.
3
Congratulations! You have found a typo in Arora and Barak's long textbook. There are likely many more.
Arora and Barak are not completely correct that the regime $S(n) \leq \log n$ is not interesting. In fact, what we do know is that the regime $S(n) = o(\log\log n)$ is not interesting, since Turing machines using that much space can only accept regular ...
3
First of all, when we reduce problem $A$ to $B$ in polynomial time, we display it by $A\le_p B$, it's means that complexity of any algorithm for solving problem $B$ is at least hard as problem $A$. From this we act as follow:
Suppose you are Given un-dircted weighted graph $G=(V,E,M,\omega)$ with weight function $\omega:E\to \mathbb{R}$, and $k_1=k_2=M$. ...
1
It seems that reduction SAT to 0-1 programming contains a mistake.
Let we have a simple formula of 1 clause: (x V y V z).
Following the Karp's reduction, we will get the equation
x + y + z = 1, which is not eqivalent to the source boolean formula,
However the unequality x + y + x >= 1 is equivalent.
1
I think your problem is NP-hard for k = 1 since that is equivalent to SAT, but it is in P for k > 1.
For example, a SAT instance can be easily decomposed into two satisfiable subformulas. Go from SAT to 3SAT using the usual methods, unit propagate, then sort what remains into Horn and anti-Horn sets, each of which is trivially satisfiable (or can be made ...
2
Let $\langle S, t\rangle$ be an instance of subset sum, where $S = \{x_1, \dots, x_n\}$, and $t, x_1, \dots, x_n \in \mathbb{N}^+$.
Create a graph $G = (V,E)$ where $V = \{u,v\} \cup S$ and $E$ contains:
The edge $(u,v)$ of weight $0$.
For each $x_i \in S$, an edge $(u, x_i)$ of weight $x_i$.
For each $x_i \in S$, an edge $(v, x_i)$ of weight $0$.
...
1
Try to think what happens when $k_1=k_2$. It makes the question much more difficult.
In fact, consider the following reduction from subset sum: Say we have a set of numbers $S=\{a_1,\dots,a_n\}$ and a target value $t$. Let us choose $k_1=k_2=t$, and build the following graph $G$:
$G$ will have $n+1$ nodes: a special node will be called $v$, and another node $...
Top 50 recent answers are included
