32

For 9x9 Sudoku, no. It is finite so can be solved in $O(1)$ time. But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial time, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 \times n^2$ Sudoku is NP-complete. The proof of NP-completeness ...


26

As there are no strings in $\emptyset$, any machine that computes it always rejects, so we can't map Yes-instance of other problems to anything. Similarly for $\Sigma^{\ast}$ there's nothing to map No-instances to.


26

It is indeed possible to use a general Sudoku solver to solve instances of TSP, and if this solver takes polynomial time then the whole process will as well (in complexity terminology, there is a polynomial-time reduction from TSP to Sudoku). This is because Sudoku is NP-complete and TSP is in NP. But as is usually the case in this area, looking at the ...


21

Chapter 2 of the SAT Handbook (by Steven Prestwich) covers how to turn discrete decision problems into CNF, in some depth. (Unfortunately, I don't think there is a draft version online -- probably best to consult your local library.) Several of the other references cited in Magnus Björk's quirky overview Successful SAT Encoding Techniques are also useful. ...


19

There are (at least) two different notions of NP-hardness. The usual notion, which uses Karp reductions, states that a language $L$ is NP-hard if every language in NP Karp-reduces to $L$. If we change Karp reductions to Cook reductions, we get a different notion. Every language which is Karp-NP-hard is also Cook-NP-hard, but the converse is probably false. ...


19

The Special Case Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity function. The intuition behind this is clear: the general case is at least as hard as the special case. In "practice", we are given $L_2$ and are stuck with ...


18

As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number in R. From that we can create an (infinite but) countable list of numbers in R. Now we can apply Cantor's diagonal argument directly to prove that there still ...


17

Don't worry – everybody gets confused by the direction of reductions. Even people who've been working in algorithms and complexity for decades occasionally have a, "Wait, were we supposed to be reducing $A$ to $B$ or $B$ to $A$?" moment. Reducing $A$ to $B$ produces a statement of the form "If I could solve $B$, then I'd also ...


17

It's actually much simpler. There's only a countable number of algorithms. Yet there are uncountably many real numbers. So if you try to pair them up, some real numbers will be left hanging.


16

To put it informally, $A\leq_{\mathrm{T}}B$ means "If I had a subroutine for $B$, then I could solve $A$", whereas $A\leq_{\mathrm{m}}B$ means, "If I had a subroutine for $B$, then I could solve $A$ using a program that calls the subroutine only once and, furthermore, just returns the answer of the subroutine without doing any further ...


15

Leveraging a known nearby problem When faced with a problem that feels hard, it is often a good idea to try to search for a similar problem that is already proven hard. Or, perhaps you can immediately see that a problem is very similar to a known problem. Example problem Consider a problem $$\text{DOUBLE-SAT} = \{ \varphi \mid \varphi \text{ is a ...


15

Unless you're translating mathematical problems to SAT instances as a learning exercise, your time will be much more fruitfully spent learning about satisfiability modulo theories. SMT will allow you to express equations and other constraints much more naturally than as Boolean SAT instances. Some SMT solvers support existential and universal quantifiers, ...


14

0-1 ILP formulated as: Does there exist a vector $\mathbf{x}$, subject to constraints: $$ \left.\begin{array}{rrrrr|rr} a_{11} x_1 & + &a_{12} x_2 & ... + & a_{1n} x_n\le b_1 \\ a_{21} x_1 & + &a_{22} x_2 & ... + & a_{2n} x_n\le b_2 \\ ...\\ a_{m1} x_1 & + &a_{m2} x_2 & ... + & a_{mn} x_n\...


13

A comment mentions a reduction from X3C to SUBSET PRODUCT attributed to Yao. Given the target of the reduction it wasn't hard to guess what the reduction was likely to have been. Definitions: EXACT COVER BY 3-SETS (X3C) Given a finite set $X$ with $|X|$ a multiple of 3, and a collection $C$ of 3-element subsets of $X$, does $C$ contain an exact cover $C'$ ...


12

This is kind of a broad question, and there are a lot of well-written references. This answer is just a basic starting point. Intuitively, when we reduce a problem $A$ to a problem $B$, we mean that if we know how to solve $B$, this somehow induces a solution to $A$ (the "somehow" is the reduction). Taking the contra-positive, this also means that if we ...


12

I would say very definitely teach using Karp (many-one) reductions. Regardless of the benefits of using poly-time Turing reductions (Cook), Karp reductions are the standard model. Everybody uses Karp and the main pitfall of teaching Cook is that you'll end up with a whole class of students who become pathologically confused whenever they read a textbook or ...


11

For example sets $H = \{x \, | $ Turing machine with index $x$ halts on input $x\}$ and $\overline{H} = \{x \, | $ Turing machine with index $x$ doesn't halt on input $x\}$. Because if $\overline{H} \leq_m H$, then $\overline{H}$ would be recursively enumerable and therefore $H$ would be recursive, which is contradiction. On the other hand $\overline{H} \...


11

You actually already have a reduction from special to general. By setting $s=0$, you are basically using the general algorithm to solve the special problem. For the other way round (i.e. a reduction from general to special): Suppose you are given a set $S = \{x_1, \dots, x_n\}$ and a number $K$ and you have to determine if there is some subset of $S$ which ...


11

The deterministic time hierarchy theorem precludes all problems in P being decided in linear time. If you try to reduce a problem to HORN-SAT that requires more than linear time to decide, you'll find that the reduction itself requires more than linear time.


11

Because log-space reductions don't necessarily run in linear time. If you take a problem in P and try to reduce it to HORN-SAT, there will be a log-space reduction, but that reduction might take more than linear time. Thus even though HORN-SAT can be solved in linear time, the other problem might not be solvable in linear time: you can convert it into a ...


10

Let $A$ be any P-complete problem (say circuit evaluation). Here are two other P-complete problems: $A_0 = \{0x : x \in A \}$ and $A_1 = \{1x : x \in A\}$. The problem $A_0 \cap A_1 = \emptyset$, while definitely in P, isn't P-complete. The latter is true even if we allow Turing reductions, assuming $L \neq P$.


10

The reason that $A$ is not defined as in NP is that we use a finer notion for NP-completeness, which is mapping (Karp) reductions. Intuitively, in a Karp reduction, we not only want the problem $A$ to be solvable using an oracle for $B$, but we also require that this oracle is only used once, and only as the very last operation. Why this notion and not ...


10

This is a sketch of a reduction from MONOTONE CUBIC PLANAR 1-3 SAT : Definition [1-3 SAT problem]: Input: A 3-CNF formula $\varphi = C_1 \land C_2 \land ... \land C_m$, in which every clause $C_j$ contains exactly three literals: $C_j = (\ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3})$. Question: Does there exist a satisfying assignment for $\varphi$ such that ...


9

According to [1]: Yes it is I also cite the same reference: Comments: There is a subtle technical distinction between this and Problem 42: the former case has a pseudo-efficient algorithm obtained by allowing numbers to be represented in unary; unless all NP-complete problems can be solved by fast algorithms, however, the Subset Product Problem, cannot be ...


9

Here's a hint: Consider Vertex Cover, which is NP-complete. If $G = (V,E)$ has a vertex cover of size $k$, then you can remove $k$ vertices from $G$ to obtain $G'$ such that $G'$ is an edgeless graph on $n-k$ vertices. Edit: The correct reduction (by using Vertex Cover) shows the problem to be NP-hard. Given the correct witnesses, you can easily show ...


9

A search problem is defined by a relation like $R$. The task is given an input $x$ find a solution $y$ s.t. $R(x,y)$ is true. A counting problem is defined as counting the number of solutions of a search problem, i.e. given an input $x$ we want to compute the number of $y$s s.t. $R(x,y)$ holds. The counting problem associated with search problem $R$ is ...


9

As Hendrik Jan mentioned, there are in fact different degrees of undecidability. For example, the problem of deciding whether a Turing machine stops on all inputs is harder than the halting problem, in the following sense: even given an oracle to the halting problem, we can't decide whether a given Turing machine stops on all inputs. One important technique ...


9

Every NP-complete program $A$ is co-NP hard under Cook reductions: given a problem $B$ in co-NP, its complement $\overline{B}$ is in NP, so there is a polytime function $f$ such that $f(x) \in A$ iff $x \in \overline{B}$. Therefore the following is a Cook reduction from $B$ to $A$: given $x$, ask whether $f(x) \in A$, and return the opposite. This shows ...


9

I believe the asker is wanting to know specifically why the standard approach to reducing $\text{SAT}$ to $\text{3SAT}$ does not continue to extend to the $\text{2SAT}$ case. Here is a walkthrough as to why. Conversion of a SAT Instance to a 3-SAT Instance: For convenience, let us assume everything is in $\text{CNF}$, or conjunctive normal form. The $\text{...


9

It is better to teach both! A computer science major should know about both of them. I don't know anyone who uses Cook reductions for teaching NP-completeness, complexity theorists obviously don't, non-complexity theorists typically follow what is the standard definition since Karp's paper and is used in all textbooks (that I know of). It will cause a lot ...


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