Share Your Experience: Take the 2024 Developer Survey

# Tag Info

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 ...
• 161k

### 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 ...
• 520
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 ...
• 81.8k
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 ...
• 2,521
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 ...
• 81.8k

### 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.
• 1,058
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. ...
• 277k
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 ...
• 8,091

### 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,...
• 277k
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 ...
• 277k
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 ...
• 161k

### 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 ...
• 277k

### 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$, ...
• 29.8k
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-...
• 1,807
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 ...
• 13.4k
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 ...
• 161k
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 ...
• 81.8k
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$...
• 86

### 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.
• 277k
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 ...
• 277k
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)$. ...
• 13.4k
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 ...
• 81.8k
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 ...
• 156

### 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 ...
• 5,390
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.
• 16.5k
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 ...
• 13.6k

### 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 "...
• 7,455

### 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 ...
• 652
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 ...
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 ...