Questions tagged [reductions]

A reduction is the transformation of one problem into another problem. A example of using a reduction would be to be to show if a problem P is undecidable. This would be achieved by transforming or performing a reduction of a decision problem $P$ into an undecidable problem. If this can be achieved then we have shown that this problem P is undecidable.

Filter by
Sorted by
Tagged with
10
votes
3answers
380 views

Reductions of hard problems to physical models

I am looking for examples of hard problems (in NP or harder) from computer science which can be reduced to models of physical processes. For example, max-2-sat can be reduced to energy minimization ...
12
votes
1answer
1k views

Unique SAT vs Exactly $m$ models

Unique SAT is the well known problem : given a CNF formula $F$, is it true that $F$ has exactly one model ? I am interested in « Exactly $m$-SAT » problem : given a CNF formula $F$ and an integer $m&...
7
votes
1answer
149 views

FL with polynomial number of log-space "reductions" still in FL?

Suppose that $f: X \rightarrow X$ is computable in log-space. Given an input $x \in X$ where $x$ is encoded within $n$ bits, is $f^n(x)$ computable in log-space?
1
vote
1answer
622 views

1- in -$k$ SAT to $k$-SAT reduction

The reduction from $k$-SAT to 1-in-$k$ SAT is known. Would you help me to find a reduction from 1-in-$k$ SAT to $k$-SAT ? Thanks.
2
votes
1answer
496 views

Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover

In the paper The diameter of random regular graphs, Bollobás and Fernandez De La Vega give asymptotic lower and upper bounds on the diameter $d$ of random $r$-regular graphs. Roughly, the lower bound ...
29
votes
2answers
1k views

Derandomizing Valiant-Vazirani?

The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an ...
7
votes
1answer
365 views

Separation between existence of crypto primitives

I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My ...
17
votes
2answers
3k views

Can strong NP-hardness really be shown using plain polytime reductions?

I recently read a proof that intended to show that a problem was strongly NP-hard, simply by reducing to it (in polynomial time) from a strongly NP-hard problem. This didn’t make any sense to me. I ...
21
votes
5answers
29k views

Direct SAT to 3-SAT reduction

Here the goal is to reduce an arbitrary SAT problem to 3-SAT in polynomial time using the fewest number of clauses and variables. My question is motivated by curiosity. Less formally, I would like ...
34
votes
5answers
5k views

Fast Reduction from RSA to SAT

Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention: Build a public library of 3SAT instances, with as few variables ...
1
vote
1answer
448 views

Complexity of Turing self-reducibility of Clique problem?

I'm interested in the complexity of self reducibility of a variant clique problem. Namely, the NP-complete problem HALF Clique: given a graph on $N$ nodes, Is there a clique of size $N/2$ in the graph?...
1
vote
1answer
500 views

Complexity class when reducing decision problem to function problem

Given a decision problem DEC which is PSPACE-Hard and a function problem FUN. If there is a polytime reduction from DEC to FUN, does this mean that FUN is FPSPACE-Hard? In my case, the answer of the ...
6
votes
0answers
341 views

Oracle complexity classes and hardness under different notions of reduction

Let C be a complexity class, and let L be a language such that PC ⊆ PL. Then it’s natural (and easy to prove) that L is C-hard with respect to Cook reductions (polytime Turing reductions). This ...
16
votes
3answers
398 views

Any references for techniques in FPT reductions?

As everyone knows, Garey and Johnson's famous book (and many others) provides an excellent reference for reduction technique in classical setting. Are there any surveys or books on the topic of ...
3
votes
2answers
846 views

Exercises of polynomial and turing reductions

I'm following a graduated course in theoretical computer sicence. A good part the theory we see in this course has to do with polynomial and Turing reductions of NP problem (to prove NP-completeness), ...
20
votes
3answers
1k views

Problems that are NP-complete under randomized or P/poly reductions.

In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which ...
11
votes
1answer
767 views

Why do NP-complete problems not have similar approximation ratios?

Since 2 NP-complete problems are by definition reducible to each other, so a solution to one of them can be obtained by using a black-box solving the other one, why don't they have similar ...
11
votes
5answers
805 views

Instance of FPT-reductions that is not a polynomial-time reduction

In parametrized complexity people use fixed-parameter-tractable (FPT) reduction to prove W[t]-hardness. Theoretically a FPT-reduction is not a polynomial-time reduction, since it can run exponentially ...
40
votes
2answers
5k views

Sum-of-square-roots-hard problems?

The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater ...
2
votes
1answer
809 views

How to prove fooling set problem to be NP-hard

I read in a paper showing that it can be implemented by reducing induced matching problem on bipartite graphs to fooling set. But the proof was omitted in that paper and I cannot find answer by myself....
10
votes
1answer
749 views

Any SAT/SMT formulations of the VRP/VRPTW (TSP, Job-Shop-Scheduling)?

i wonder if they are any approaches formulating a Vehicle-Routing-Problem with Time-Windows (VRPTW) (as a decision problem) as a SAT/SMT instance? (alternative: TSP) For example: "Is there a valid ...
5
votes
0answers
858 views

Contained in NP and Turing-reduction from an NP-complete problem $\Rightarrow$ NP-complete under Karp reductions? [duplicate]

Possible Duplicates: Do many-one reductions and Turing reductions define the same class NPC Many-one reductions vs. Turing reductions to define NPC Let $P,Q \subseteq \Sigma^*$ be languages ...
24
votes
2answers
911 views

Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?

Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent. Since finding a perfect matching in a non-bipartite graph is in NP, there exists ...
6
votes
2answers
390 views

PCPs with imperfect completeness

The traditional definition of PCPs have perfect completeness -- If $x\in L$, then the prover can give a proof on which the verifier (on reading constantly many bits) always accepts. Suppose we modify ...
0
votes
1answer
1k views

Question about Mapping Reductions (Clarify Example)

I cannot for the life of me wrap my head around these reductions. Specifically, the example I'm wrestling with: ...
22
votes
1answer
1k views

Binary multiplication and parity convolution

This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a ...
1
vote
1answer
1k views

Removing all but a few cycles in a graph

Let problem $S$ be defined as Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the ...
3
votes
2answers
4k views

Using decision version of TSP to solve optimization version

Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP. This is not a homework assignment, but of general interest. I have been trying ...
14
votes
1answer
910 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
7
votes
1answer
3k views

Simple reduction to unbounded knapsack?

Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited ...
22
votes
9answers
1k views

Reductions from the book.

This is along the lines of "Algorithms from the Book". Although reductions are algorithms as well, I thought it doubtful that one would think of a reduction in response to the question about ...
11
votes
6answers
2k views

Do many-one reductions and Turing reductions define the same class NPC

I wonder if NPC classes defined by many-one reductions and Turing reductions are equal. Edit: Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class ...
5
votes
1answer
1k views

Is there any natural Karp reduction from Independent Set problem to SAT?

Is there a natural Karp reduction from Independent Set to SAT ? That is, a reduction that does not rely on the Turing machine (as the case in proof of Cook's theorem) but the combinatorial structure.
41
votes
7answers
6k views

Many-one reductions vs. Turing reductions to define NPC

Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?

1 2 3
4