The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

### Why can't we prove SAT is NP complete just using the Tseytin Transformation?

NP-complete is defined with respect to Turing machines, not circuits. NP-complete specified in terms of polynomial-time algorithms, where polynomial-time algorithms are formalized as Turing machines ...
• 163k
Accepted

### Proofs of reduction of any hard problem

The first "approach" is the definition of a polynomial time many-one reduction. This is the type of reductions used for defining NP-hardness: a problem $B$ is NP-hard if for every problem $A$...
• 278k
Accepted

### Is there such a notion as "effectively computable reductions" or would this be not useful

Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations ...
• 7,138
Accepted

### SAT satisfaction with 10 variables

The problem you mentioned is in $P$ so it is not NP-complete. We know that $|\phi| = n$ so the number of variables is less than $n$ and we know that members of $A$ exactly have 10 True assignments. So ...
Accepted

### Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ ...
• 29.6k
Accepted

### CLIQUE $\leq_p$ SAT

There are many ways to reduce CLIQUE to SAT. Probably the simplest is as follows. Suppose that we have a graph $G = (V,E)$, and interested in a $k$-clique. We will have $k|V|$ variables $x_{iv}$, ...
• 278k

### Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

Morandini, NP-complete problem: partition into triangles shows that the following problem is NP-complete: Given a tripartite graph $G$ on $3n$ vertices (given together with a tripartition), determine ...
• 278k
Accepted

### Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

Let's flip this around using the fact that $L$ is $\text{NP}$-hard iff $\overline{L}$ is $\text{coNP}$-hard. You want to show that $$\text{3-Col} \cup \overline{\text{4-Col}} \text{ is NP-hard}.$$ To ...

### Concrete example of Vertex Cover to Subset Sum reduction

In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem... We do? ... mostly to prove Subset Sum is NP-Complete. There's no ...

• 183

### If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$

By hypothesis $Q \le_p L$, i.e., there exists a poly-time computable function $f(x)$ such that $x \in L \iff f(x) \in Q$. Then:  x \in \overline{L} \iff x \not\in L \iff f(x) \not\in Q \iff f(x) \...
• 29.6k

### Reducing Vertex Cover to Half Vertex Cover

In addition to the reduction given by Yuval Filmus, you can also use the following reduction, which avoids blowing up the size of $G$ to $\Theta(|V| \cdot |E|)$. Assume w.l.o.g. that $k<|V|$ (...
• 29.6k

### Polynomial-Time reduction from Partition to MakeSpan

Given an instance of partition (i.e., a set of numbers) $\{a_1, \dots, a_n\}$ create an instance of Job Scheduling (what you call Makespan) with $2$ machines and $n$ jobs $j_1, \dots, j_n$, where the ...
• 29.6k