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 a undecidable problem. If this can be achieved ...

learn more… | top users | synonyms

1
vote
1answer
181 views

Is there simple reduction Dominating Set to Vertex Cover?

Is there simple reduction Dominating Set to Vertex Cover? In the other direction the reduction is simple. Searching the web returned blog. It warns This is not finished yet and experiments ...
2
votes
1answer
74 views

Proof of an Ising model representation of graph isomorphism problem

I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two ...
6
votes
3answers
169 views

Solving problems by deciding a logic

I am curious to know when open problems have been solved by expressing them in a specific logic, and then showing that this logic is decidable. I have two distinct cases in mind: The problem is ...
6
votes
0answers
81 views

What is known about reduction by “$P_1$ interprets $P_2$” for generalized programming languages?

Inspired by this answer, let's say that a programming language is given by the data $L=(P,ev)$ where $P$ (the set of "valid programs") is a computable subset of $\Sigma^*$ and $ev$ (the "evaluator") ...
3
votes
2answers
153 views

Root finding in [0,1]

I am interested in the problem of finding a real root of a polynomial equation $f(x)=0$ where $f(x)=\sum_{i=0}^n a_ix^i$. Is it possible to give a reduction, i.e, to compute a different polynomial $g$ ...
2
votes
0answers
103 views

Graph partition with objective over intra-partition weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
0
votes
0answers
45 views

Polynomial ILP formulation of a maximum over polynomial ILP problems?

I have an optimization problem $P$ which I've polynomially reduced to three equivalent formulations: A maximum-weight maximum-cardinality bipartite matching A maximum-cost maximum-flow network An ...
0
votes
0answers
37 views

On Equivalence of “gen-CONF” problem and “DH-exp-inv” problem

Let $g$ be a generator of a group of prime order $p$; $a,b ∈_R Z_p^+$ Consider an Algorithm $\mathcal{A}$ which on input $g,g^a,g^{ab}$ outputs $g^{br},r$, for some non zero $r ∈ Z_p$ And an ...
0
votes
0answers
56 views

Direct reduction from Circuit SAT to NAE-3-SAT

I know how to reduce $Circuit-SAT$ problem to $3-SAT$ and thereafter to reduce $3-SAT$ to $NAE-4-SAT$ and finally $NAE-3-SAT$. What I do is that I rewrite the circuit to comprise only of NAND (which ...
7
votes
1answer
233 views

NP-hardness proof: looking for some good restricted np-hard problems

To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can ...
12
votes
5answers
641 views

Should reductions make us more or less optimistic for the tractability of a problem?

It seems to me that most complexity theorists generally believe the following philosophical rule: If we can't figure out an efficient algorithm for problem $A$, and we can reduce problem $A$ to ...
3
votes
3answers
118 views

On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$

I am trying to prove the following Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$ where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group ...
6
votes
1answer
163 views

Max-weight connected subgraph problem in planar graphs

The maximum-weight connected subgraph problem is as follows: Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$. Output: a maximum-weight subset $S$ of ...
26
votes
7answers
1k views

Nontrivial membership in NP

Is there an example of a language which is in $NP$, but where we cannot prove this fact directly by showing that there exists a polynomial witness for membership in this language? Instead, the fact ...
13
votes
3answers
304 views

Can limit of hard languages be easy?

Can the following all hold simultaneously? $L_s$ is contained in $L_{s+1}$ for all positive integers $s$. $L = \bigcup_s L_s$ is the language of all finite words over $\{0,1\}$. There is some ...
13
votes
3answers
558 views

Transitive feedback arc set (TFAS): NP-complete?

Some time ago, I posted a reference request for graph problems where we want to find a 2-partition of the edges where both sets fulfill a property not related to their cardinality. I was trying to ...
8
votes
0answers
178 views

A reduction between small cliques problems

I'm looking for a reduction that gets a graph $G=(V_G,E_G)$ and outputs a graph $H$ that satisfies the following requirements. If $G$ contains a triangle, then $H$ contains a clique of size 9. If ...
3
votes
1answer
197 views

Maximize the expected number of “losers” - Is it NP-hard?

I am trying to find a reduction for a problem that seems NP-hard: Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$. You want to choose two pairs out of the three pairs and ...
4
votes
1answer
162 views

On Random Self-reducible properties

Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$. 1) Is $k$-sum random self-reducible? That ...
3
votes
1answer
93 views

Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?

Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient ...
-1
votes
1answer
177 views

Graph Isomorphism: Polynomial time reduction from GI for disconnected graphs to GI for connected graphs? [closed]

Let the Graph Isomorphism Problem be the problem to decide whether there is a one-to-one mapping between the vertices of two graphs that preserves the edge relations. Let the Graph Isomorphism ...
0
votes
0answers
160 views

Technical clarification on Promise problems

$xSAT$ is a problem in $NP\cap coNP$ defined by Even, Selman and Yacobi in http://www.sciencedirect.com/science/article/pii/S001999588480056X. Consider $\Pi$ to be the problem to decide if there is ...
11
votes
3answers
261 views

Is there a reduction to “door and pressure plate” games that doesn't explode solution length?

This paper gives a proof that in a game with doors and pressure plates, it is PSPACE-hard to determine whether or not the (player's) avatar can reach a given location. This is proven by a reduction ...
20
votes
6answers
785 views

Advanced techniques for determining complexity lower bounds

Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level. Beyond the "simpler" ...
7
votes
0answers
109 views

$\mathsf{TC^0}$-completeness and reductions

AFAIU, we don't know any problem which is complete for $\mathsf{TC^0}$ w.r.t. many-one $\mathsf{AC^0}$ reductions ($\leq^\mathsf{AC^0}_m$). On the other hand, proving that they don't exist would ...
11
votes
1answer
160 views

What is the minimum required depth of reductions for NP-hardness of SAT?

As everyone knows, SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions. It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions. My questions is what is the minimum ...
4
votes
1answer
171 views

Complexity reductions to Hamiltonian Path?

I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path. Do ...
12
votes
1answer
336 views

Is there a list of canonical problems in distributed systems?

Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about Solved Problems, Unsolved Problems and Non-Problems in Concurrency. The paper is easily readable, but ...
10
votes
3answers
1k views

Subset sum vs. Subset product (strong vs. weak NP hardness)

I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard. Subset Sum: Given $X = ...
1
vote
0answers
138 views

Is there a tight lower bound on the complexity of SSSP on a graph?

I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to ...
33
votes
3answers
726 views

Why does randomness have stronger effect on reductions than on algorithms?

It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite ...
11
votes
3answers
440 views

Does NP-completeness/hardness have to be constructive?

Is there any $L\in {\bf NP}$ with the following properties: It is known that $L\in {\bf P}$ implies ${\bf P}={\bf NP}$. There is no (known) polynomial time Turing reduction of $SAT$ (or some other ...
3
votes
1answer
140 views

Cook reduction for search problems, by universal property?

A search problem is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ solves $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be ...
-3
votes
1answer
101 views

Difference between 'Reductions' in algebraic problems vs “Reductions” in Computational Intractability [closed]

When I read NP-completeness for the first time, I really wondered why is the concept of Reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special ...
22
votes
2answers
907 views

Natural CLIQUE to k-Color reduction

There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. ...
3
votes
0answers
119 views

Counting reduction maintaining the length of the witness for #Knapsack

I want to know if there is counting reduction (weakly or strongly parsimonious) maintaining the length of the witness between two variations of $\#Knapsack$ problem. Let me define the problems first ...
4
votes
1answer
438 views

Counting reduction from #SAT to #HornSAT?

Is it possible to find a counting reduction from #SAT to #HornSAT? I haven't found this question posted here, so decided to check if anyone has any answer to this. Let me explain what do I mean by ...
-4
votes
1answer
407 views

Are all complexity classes closed under a particular reduction? [closed]

We are given a ${\bf \it syntactic }$ complexity class ${\bf A}$ such that ${\bf P}$ $\subseteq$ ${\bf A}$ $\subseteq$ ${\bf PSPACE}$. Is it possible that ${\bf A}$ is ${\bf \it not}$ closed under any ...
1
vote
1answer
186 views

Super-logspace mapping reducibility

There are two well-known mapping reducibilities: polytime and logspace. In both cases, the length of the output string can be at most polynomial in the length of a given input string. If we allow to ...
5
votes
0answers
117 views

What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions. Since ...
4
votes
1answer
294 views

Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET

There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at http://en.wikipedia.org/wiki/Dominating_set#L-reductions (attributed there to Kann 1992, but seen, for ...
1
vote
3answers
440 views

what is “one-to-one reduction from a function f to another function g”

I am reading a paper called "Rational Proof". It mentioned the following one-to-one reduction. I cannot google an introduction of it. An excerpt from the paper. "Recall that a one-to-one reduction ...
2
votes
1answer
198 views

Reduction/transformation from MinCostSat to MaxSat

I recently ran into MaxSAT competitions website and was looking into the problem formulation. I vaguely remember reading somewhere that MinCostSAT and MaxSAT are related to each other and one can be ...
6
votes
1answer
337 views

More efficient Cook-Levin reduction

In the Arora-Barak book, in the Cook-Levin reduction, the resulting SAT formula is of size $T(n)\log(T(n))$, where $T(n)$ is the running time of the given Turing machine. Is there a method to get a ...
5
votes
1answer
290 views

Are there non-closed complexity classes for which there are complete problems?

Is saying that a class is non closed analogous to stating there are complete problems that have not been identified for that class under a certain type of reduction?
7
votes
2answers
711 views

What does 'gadget' mean in NP-hard reduction?

This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a ...
8
votes
3answers
318 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 ...
11
votes
1answer
930 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 ...
7
votes
1answer
131 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
296 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.