Skip to main content
Share Your Experience: Take the 2024 Developer Survey
30 votes
Accepted

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

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 ...
D.W.'s user avatar
  • 161k
25 votes

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

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 ...
rlms's user avatar
  • 520
20 votes
Accepted

The 'directionality' of reductions?

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 ...
David Richerby's user avatar
18 votes
Accepted

How to prove the existence of a number which cannot be written by any algorithm?

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 ...
Albert Hendriks's user avatar
17 votes
Accepted

Why does many to one reduction imply Turing reducibility?

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 ...
David Richerby's user avatar
17 votes

How to prove the existence of a number which cannot be written by any algorithm?

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.
Sebastian Oberhoff's user avatar
12 votes
Accepted

Reduction 3SAT and CLIQUE

Here is one possible way to reduce Clique to SAT (you can then further reduce it to 3SAT). This type of reduction is often used in (propositional) proof complexity, an area of complexity theory. ...
Yuval Filmus's user avatar
11 votes
Accepted

reduction from 3-SAT to Subset Sum problem

The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that ...
Kyle Jones's user avatar
  • 8,091
10 votes

P=NP, isn't it?

Every CNF is falsifiable (choose a clause and choose a truth assignment which falsifies it). Unfortunately, the opposite of "CNF $\varphi$ is satisfiable" is not "CNF $\varphi$ is falsifiable". Rather,...
Yuval Filmus's user avatar
9 votes
Accepted

Can we have a poly time reduction from 2-SAT to 2-Coloring problem?

As rotia mentions in their comment, to make the question meaningful we must restrict the power of the allowable reductions. The two most obvious choices are to allow only logspace reductions or only ...
Yuval Filmus's user avatar
9 votes
Accepted

Is it decidable whether a Turing machine modifies the tape, on a particular input?

Yes, this is decidable. Here are two different proofs of that fact. A counting proof Define a configuration to be the state of the tape, the location of $M$'s head, the state that $M$'s finite ...
D.W.'s user avatar
  • 161k
9 votes

How to prove the existence of a number which cannot be written by any algorithm?

Consider the number whose $k$th digit is $1$ if the $k$th Turing machine halts on the empty input, and $0$ if it doesn't halt. If you could generate the digits of this real number then you could solve ...
Yuval Filmus's user avatar
8 votes

Can we reduce an NP complete item to an NP item which is $\bf{non}$ P?

No, it is not possible to prove that all $NP$ problems which are not $P$ are $NP$-complete. In fact, the opposite has been shown: unless $P=NP$, there are $NP$ intermediate problems, neither in $P$, ...
Joey Eremondi's user avatar
8 votes
Accepted

Is finding a set cover of size $k$ NP-complete?

Yes, it remains NP-complete, even under the restriction that all subsets of a specific size $s$ (which translates to immediately requiring that $k = n / s$. For example, for $k = n / 3$, 3-...
aelguindy's user avatar
  • 1,807
8 votes
Accepted

Is every PSPACE-complete problem complete with respect to logspace reductions?

If every PSPACE complete problem is also complete under logspace reduction, then $\mathsf{P\neq PSPACE}$. To see why, suppose for the purpose of contradiction that the definition of completeness ...
Ariel's user avatar
  • 13.4k
8 votes
Accepted

What does "AC0 many-one reduction" mean?

An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time many-one reduction, except that instead of requiring that the mapping ...
D.W.'s user avatar
  • 161k
7 votes
Accepted

Is every undecidable language reducible to any other undecidable language?

There is no concept of "reducibility in general". You always have to specify the power of the reduction. For example, if you allow mapping reductions but with literally any function (not necessarily a ...
David Richerby's user avatar
7 votes
Accepted

Reducing max flow to bipartite matching?

Strangely enough, no such reduction is known. However, in a recent paper, Madry (FOCS 2013), showed how to reduce maximum flow in unit-capacity graphs to (logarithmically many instances of) maximum $b$...
dwajc's user avatar
  • 86
7 votes

Why does a reduction from a P-problem to an NP-complete problem not show that P=NP?

Part 1 shows how to solve BoxDepth using MaxClique. Part 2 shows how to solve BoxDepth directly. None of the parts says anything about solving MaxClique.
Yuval Filmus's user avatar
7 votes
Accepted

How to partition a set into disjoints subsets each of given size?

When $s_j = 1$ for all $j$, the problem is the same as deciding whether a bipartite graph has a perfect matching. In the general case, we can solve it using maximum flow. Set up a flow network with ...
Yuval Filmus's user avatar
7 votes
Accepted

What is the purpose of interpreting elements in the proof of reduction of PCP to validity decidability problem of predicate logic?

Lets start with what exactly you are trying to prove. You're dealing with a signature $\sigma$ which consists of one constant $e$, two function symbols $f_0,f_1$, and one binary predicate $P(s,t)$. ...
Ariel's user avatar
  • 13.4k
7 votes
Accepted

Can we use exponential function in a reduction?

For the sake of notation, I'm going to assume you're trying to produce a polynomial time reduction $f$, which that maps instances $x$ of some problem $L_1$ to instances $f(x)$ of ...
David Richerby's user avatar
7 votes
Accepted

Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP?

There is no guarantee that the packing algorithm you suggested will lead to an optimal packing. Say you have two knapsacks of capacity 5, and objects of size 1, 2, 3 and 4. An optimal packing would be ...
Dylan Black's user avatar
7 votes

What does "AC0 many-one reduction" mean?

The "what is" part of the question was succinctly answered by D.W.: An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time ...
Thomas Klimpel's user avatar
7 votes
Accepted

So if a problem is more difficult the language it represents is smaller?

$L_1$ and $L_2$ are always countably infinite, and thus "equally big". If any language is finite, then it is "constant time" recognizable.
Pål GD's user avatar
  • 16.5k
7 votes
Accepted

Is this partitioning problem NP-complete?

This problem can be solved in polynomial time with dynamic programming. Let $A[i]$ be the maximum value you can achieve with the points $x_1, \dots, x_i$. You can compute $A[i]$ by choosing the ...
orlp's user avatar
  • 13.6k
7 votes

Prove that "Finishing the degree in three years" problem is NP-Complete

Consider an instance $(G,k)$ of the clique problem: deciding whether there is a clique of size $k$ in the graph $G$. Construct a course for each vertex (say "vertex course") and for each edge (say "...
xskxzr's user avatar
  • 7,455
7 votes

Solving the min edge cover using the maximum matching algorithm

Assume, w.l.o.g., that G=(V,E) is a graph without isolated vertex. Let's denote by $\mathcal{A}$ the algorithm you describe in your question. We seek to prove that given $G$, $\mathcal{A}$ outputs a ...
Mengfan Ma's user avatar
7 votes
Accepted

Can current quantum computers decide languages that Turing Machines cannot?

No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated ...
Laakeri's user avatar
  • 1,339
6 votes

Reducing Exact Cover to Subset Sum

Basic idea: In the exact cover problem, each element is reduced to a number. Then, each set is reduced to the sum of the numbers it covers. Finally, set $k$ to be the sum of all numbers. This ...
Christopher Boo's user avatar

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