5

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$ ...


5

$P$-completeness is defined in terms of reductions stronger than polynomial reductions. For example, the notion of log-space reductions is such a "stronger" (more restrictive) reduction. Notice that all languages in $P$ are poly-reducible to each other, by definition. So defining $P$-completeness in terms of poly-reductions would just be useless - ...


4

A description is given in the first paragraph of [1], where HI stands for Hypergraph Isomorphism and GI for Graph Isomorphism: Given a pair of hypergraphs $X=(V,E)$ and $X'=(V',E')$ as instance for HI, the reduced instance of GI consists of two corresponding bipartite graphs $Y$ and $Y'$ defined as follows. The graph $Y$ has vertex set $V \uplus E$ and edge ...


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^*...


3

Let $T$ be a Turing machine. Construct a Turing machine $T'$ that simulates $T$ on the empty input word and, when (if) the simulation ends, it accepts (regardless of the input to $T'$). Notice that $T'$ can be computed from $T$. Pick $M_2$ as the Turing machine that immediately halts and accepts. Then $\{T', M_2\} \in C$ iff $L(T') = \emptyset$, which ...


3

Suppose we have a solution to the longest path problem, longest-path, in which given a graph G, and an integer k, we need to decide if G has any (simple) path of k edges. Then to solve the Hamiltonian-path problem, HAM-PATH, we could use longest-path with k=|G|-1. This means, HAM-PATH is polynomial time reducible to longest-path. $$\begin{aligned} i.e., ...


3

Sometimes we insist that the three literals in a 3SAT clause belong to different variables. This ensures, for example, that a random assignment satisfies a clause with probability exactly $7/8$. The translation $x \lor y \lor y$ doesn't satisfy this condition, but the other one does.


3

I think the whole misunderstanding comes from an incorrect definition of TFNP. TFNP is for problems like factoring, where there is always a solution. Every integer has a prime factorization, so you don't have to make any restrictions on what inputs are allowed - i.e., every input string of bits represents a number that has a factorization. This is different ...


3

Suppose you have a graph $G$ of order $n$. $G$ has a simple path of length $\geq n - 1$ if and only if $G$ has a hamiltonian path.


3

As you correctly spotted, the reduction can be implemented in polynomial time, and the blowup in the formula size is indeed linear. The reduction is also correct, with the caveat mentioned in item 2. It's not trivial to show, but we'll go at it slowly. So first, let's assume we allow this construction also for 2 literals. As for 1 literal clauses -- we can ...


2

You say: This is only possible if $A \le_m B$ exists and $B=\overline{B}$ But that condition simplifies to "false" since it can never the case that $B=\overline{B}$. Anyway the answer to both cases is "yes". If $A \le_T B$ then there is a Turing machine $T$ with oracle $B$ that decides $A$. By complementing $T$'s output we obtain a ...


2

In fact, every non-trivial language is $\text{R}$-hard. That is, every decidable language is reducible to every non-trivial language. Indeed, let $A$ be a decidable language, and let $B$ be a non-trivial language. A reduction from $A$ to $B$ operates as follows. On input $x$, check whether $x\in A$ (this can be done as $A$ is decidable), then: if $x \in A$, ...


2

As mentioned in the above comment, the format of your reduction is not correct, so you have to take care of that first, and think about it again. Also, the hint I gave in the question that you linked should be enough. Anyway, here is another hint. Hint: consider the identity reduction that maps every word $x$ to itself, and try to understand why it does not ...


2

If $M$ does not have the option to not move its head at all, as stated in a comment to the question, then the problem is trivially decidable by the Turing machine that immediately halts and accepts. If $M$ might not move its head while computing $T(w)$ and the problem is to decide whether it actually does so, then the problem must be undecidable as otherwise ...


2

It is called contraposition : $f(x) \in B \Rightarrow x \in A$ is equivalent to $x \notin A \Rightarrow f(x) \notin B$. So, the two statements that you have seen are equivalent as well.


2

Suppose your original graph $G$ has a Hamiltonian cycle $C$. Then the cost of the tour induced by $C$ in the new graph $G'$ you defined is indeed $0$ and conversely, any TSP tour of cost $0$ can only use edges of cost $0$ as you did not introduce any edges with a negative cost. Adding the loops does not change this, so the reduction works out if we are ...


2

As I understand, your problem is a decision problem defined as such: Independant set with fixed vertex (ISFV): Input: a graph $G = (V, E)$, a vertex $u \in V$, an integer $k$. Question: is there an independent set of size $k$ containing $u$? Independent set (IS) is defined as: Input: a graph $G = (V, E)$, an integer $k$. Question: is there an independent ...


2

Let $S$ be any language in $\mathsf{P}$. You are looking for a function $f$ with the following properties: $f$ can be computed in polynomial time. If $x \in S$ then $f(x) \in A$. If $x \notin S$ then $f(x) \notin A$. Since $S$ is in $\mathsf{P}$, we can determine whether $x \in S$ in polynomial time. Therefore, the reduction $f$ can work as follows: ...


2

I think there is an easy reduction from Knapsack. Knapsack: Input: a list of couples (value, weight) $\{(v_1, w_1), …, (v_n,w_n)\}$, a maximum weight $W$, a target value $V$ Question: is there a subset $S \subset [\![1, n]\!]$ such that $\sum\limits_{i\in S} v_i \geq V$ and $\sum\limits_{i\in S} w_i \leq W$ Now given an input of knapsack, let's construct ...


2

I think if you choose all $d$'s to be exactly $1$ and choose $L$ to be exactly $n$ (number of cities), any solution must visit all cities, so the reduction will work out.


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) ...


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 ...


2

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

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

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

While @nir shahar's answer is not wrong, your question is about the complexity of TAUTOLOGY when we have no assumptions on the structure of the formula. In the special case of Conjunctive Normal Form (CNF, a AND of OR clauses), you can solve TAUTOLOGY in polynomial time, as Shahar says. However, there are other special cases for which TAUTOLOGY is co-NP-...


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\...


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

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\}$...


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 ...


Only top voted, non community-wiki answers of a minimum length are eligible