New answers tagged computability
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
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
Regarding the first part.
Answer 1 is incorrect. Consider the graph $G = (\{1,2,3,4,5,6\}, \{(1,2), (1,3), (2,3), (3,4), (4, 5), (4,6) \})$. The maximum degree of $G$ is $3$ but the degree of $x_{(3,4)}$ in $\widetilde{G}$ is $4$.
Answer 2 is correct. Consider an edge $e=(u,v)$ of $G$. The number edges distinct from $e$ that are incident to $u$ (resp. $v$) ...
2
Let's check these in reverse order.
Question B: your reasoning looks good as it demonstrates that both (1) and (2) are not strong enough. The choice (4) is a possible bound, but it's not as tight as it can be. Your example is extremal in a sense that you can't make the degrees any larger, meaning that your bound is, as the question asks, "closest ...
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
To see whether a "reduction is correct and well-defined", first look at the definition: what is a reduction? In this case, you require a so-called Karp reduction or a polynomial-time reduction from Edge-Coloring to Vertex-Coloring. In particular, it must hold that (i) the process runs in polynomial time and (ii) an instance $G$ of Edge-Coloring has ...
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$) ...
1
The "key" here is to make $f$ construct a new machine $M'$ that will contain all of the primes assuming that $w\notin L(M)$, and otherwise, there will be at least one prime it rejects.
Now, the reduction $f$ will work by taking $\langle M, w\rangle$ and outputting the following TM $M'$:
On input $z$, run the following:
Emulate $M$ on $w$ for $|z|$ ...
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
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
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}.
$$
0
Rice's theorem states that if $L_S$ is not trivial (i.e., is not $\varnothing$ nor all languages) then $L_S$ can't be decided (it might be computationally enumerable, though).
An extension to Rice's theorem states that $L_S$ is computationally enumerable if and only if:
For all $L_1, L_2$ computationally enumerable, if $L_1 \in L_S$ and $L_1 \subset L_2$, ...
-1
Take a look at Rice's theorem and its extensions.
Basically, Rice's theorem and its extension state:
If $\emptyset\neq S\subset RE$ then $L_S\notin R$
If $\emptyset \neq S\subset RE$ and $\Sigma^*\notin S$ (please fix me if this is wrong, this is what I remember) then $L_S\notin RE$
4
First, note that Sipser says ""If M's language isn't empty, N will accept every input".
Let us first prove this statement:
Assume $L(M) \neq \emptyset$.
Then there exists some $x \in L(M)$. Because $L(M) \subseteq \Sigma^*$ we have $x \in \Sigma^*$. Then because $s_i \in \Sigma^*$ and $\Sigma^*=\{s_0, s_1, s_2, .... \}$, there exists an $i^*...
1
What you are complementing is the language, not $RE$ or $co-RE$.
$RE$ and $co-RE$ are families of languages. Complementing a language is not the same as complementing the family its in.
For instance, if we have a family of sets: $\mathcal{F}:=\{\{1,2\},\{3,4,5\},\{1,5\}\}$, when the "world" we live in only has $5$ elements: $W:=\{1,2,3,4,5\}$, then ...
3
Please feed this program (pseudo-code) into yours.
for every integer n > 3:
has_solution := false
for every prime p < 2*n:
if (2*n - p) is a prime:
has_solution := true
break from inner loop
if not has_solution:
halt
Congratulations! You have solved the Goldbach's conjecture!
A step-by-step analysis of your program when it is ...
2
The halting problem asks whether a particular Turing Machine will halt if given a particular input. If you don't consider the input, you can't claim to solve the halting problem; a given program might halt for some inputs and not for others.
You can substitute the input with a static initialisation without altering the sense of this objection. It's not ...
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 ...
0
It is possible to show ALL$_{TM}$ is undecidable by Rice's theorem.
Where ALL$_{TM}$ = {<M>, M is a TM and L(M) = $\Sigma^*$}
Take two TMs M$_1$ and M$_2$ where L(M$_1$) = L(M$_2$).
Because both recognize the same language,
if $<M_1>$ $\in$ ALL$_{TM}$ then $<M_2>$ is too.
if $<M_1>$ $\notin$ ALL$_{TM}$ then $<M_2>$ isn't as ...
Top 50 recent answers are included
