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.
201
questions
8
votes
3
answers
934
views
A partition problem in which some numbers may be cut
In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard.
However,...
- 2,078
7
votes
1
answer
200
views
Is Circuit Minimization $P$-hard under logspace reductions?
By Circuit Minimization, I am referring to the following decision problem.
Circuit Minimization
Input: A bit string $x$ and a number $k$.
Question: Does there exist a Boolean Circuit $C$...
- 5,127
14
votes
0
answers
469
views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
- 5,127
7
votes
1
answer
171
views
Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?
While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around:
Note that the general ...
- 300
1
vote
0
answers
59
views
Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity
I am wondering if this is a topic that has had research done...
If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...
- 111
5
votes
0
answers
119
views
Reduction between functions that preserves time and space-complexity
Under which reduction(s) is the class $\mathsf{FTISP}(t(n), s(n))$ closed?
Let $\mathsf{FTISP}(t(n), s(n))$ the class of functions from $\{0,1\}^*$ to itself that are computable by a Turing machine ...
- 4,439
8
votes
2
answers
1k
views
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks.
Isn't it straight forward to ...
- 463
4
votes
0
answers
146
views
Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$
The classic reduction from 3SAT to PLANAR-3SAT requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the crossing number inequality suggests ...
- 778
10
votes
1
answer
232
views
On sparse complete sets and P vs L
Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$. (See "Sparse complete sets for NP: Solution of a conjecture of Berman ...
- 5,127
4
votes
1
answer
189
views
Verifying that a reduction is correct
Alice has a function $f: \{0,1\}^* \to \{0,1\}^*$ which can be computed in polynomial time. She claims that $x \in \mathrm{SAT} \iff f(x) \in \mathrm{CLIQUE}$. Alice sends the circuit computing $f$ on ...
- 309
4
votes
2
answers
422
views
Random self reducibility and NP
I was reading the Wikipedia page Random self-reducibility and it states:
If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$.
I am ...
- 434
2
votes
0
answers
67
views
On reduction between two classes?
https://link.springer.com/article/10.1007/s00153-013-0351-x gives seven reductions $m,c,d,p,btt(1),\ell,tt$.
What does norm $1$ mean in $btt(1)$?
Is there illustrative examples that help understand ...
- 12.8k
2
votes
1
answer
169
views
What is conjunctive truth table reduction?
What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?
- 12.8k
2
votes
1
answer
51
views
Certainty of mutual confirmation over faulty channels?
This is a very theoretical question, although I am sure the problem pops up in lots of IT and automation applications. Still, I prefer to formulate it in an action-movie scenario (a bit of the ...
- 21
11
votes
3
answers
313
views
Calculus of Constructions: compress expression to its smallest form
I'm aware that the Calculus of Constructions is strongly normalizing, meaning every expression has a normal for that cannot be beta,eta-reduced further. So in fact this is the most efficient ...
- 213
1
vote
0
answers
81
views
Prove that finding set of $k$ vertices $S$, such that $G{\setminus}S$ is claw-free is NP-Complete
The claw in a graph $G(V,E)$ consists of a vertex $v\in V$, and it's three neighbours - $\{x_1,x_2,x_3\}\in V\setminus \{v\}$, if $\{x_1,x_2,x_3\}$ form an independent set in $G$.
The problem asks us ...
- 201
1
vote
0
answers
448
views
Reduction from k-Almost Independent Set to Independent Set
The problem of $k$-Almost Independent Set is to decide whether or not $(G,m)$ where $G$ is a graph and $m \in \mathbb{N}$ has a subset of $m$ vertices that induces a subgraph with at most $k$ edges. I ...
- 11
-3
votes
1
answer
87
views
About reduction relation between $HP$ and $\mathcal{E}\mbox{*}$ [closed]
I'm studying Theory Of Computation and have some questions in the beginning:
About reduction relation between $HP$ and $\mathcal{E}\mbox{*}$
$HP =$ {$<M,w>$ $|$ $M$ is a $TM$ and it halts on ...
1
vote
1
answer
117
views
hardness of constant approximation of largest matching set
We say that $H$ is a matching graph if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more.
Given a graph $G=(V,E)$ a subset $U\subseteq V$...
- 153
-1
votes
1
answer
135
views
A conceptual question regarding hardness proofs by reduction [closed]
If we restrict the input domain of a known NP-hard problem P so that this restricted domain is equal to the input domain of another problem S, then show that we can reduce a solution to P given input ...
17
votes
2
answers
730
views
Is intersection of $k \ge 3$ graphic matroids in P?
It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids.
...
- 173
8
votes
0
answers
784
views
A list of XP-hard problems
The class $XP$ is the class of problems parameterized by $k$ that can be solved in time $n^{f(k)}$ for some function $f$ (each $k$ may require a different algorithm).
In their book on parameterized ...
- 312
2
votes
0
answers
152
views
Many-one reducibility equivalent for more general computational problems?
Many-one reducibility, denoted by $\leq_m$, is a binary relation between 2 decision problems which is defined as follows:
$L' \leq_m L$ iff there exists a computable function $f$ (called a reduction) ...
- 65
9
votes
0
answers
918
views
What are the best known reductions from SAT to CNF-SAT?
Problems
Let SAT denote the following problem:
Given a boolean formula, does there exist a satisfying assignment?
Let CNF-SAT denote the following problem:
Given a ...
- 5,127
12
votes
1
answer
211
views
Reductions between languages of different densities?
The density of a language $X$ is a function $d_X \colon \mathbb{N} \to \mathbb{N}$ defined as $$d_X(n) = |\{x\in X \mid |x| \le n\}|.$$
Suppose $A$ and $B$ are languages over some finite alphabet, $A$ ...
- 18.9k
1
vote
2
answers
3k
views
Is iszero of the untyped lambda calculus sound and complete? [closed]
I am using the following definitions in the notation of Haskell. In case it matters, I would like to use only the $\alpha,\beta,\eta$ reductions rather than the Haskell evaluation rules.
...
- 173
4
votes
1
answer
328
views
UnambiguousSAT reductions
Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other.
Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but ...
- 12.8k
2
votes
1
answer
258
views
Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?
The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as ...
- 653
2
votes
0
answers
205
views
Reduction Unbounded Knapsack < k-Exact Unbounded Knapsack
I'd like to have an explicit reduction among these two problems:
(1) Unbounded Knapsack: Given a set of $n$ item types with weight $w_i$ and quality $q_i$ solve:
$$maximize \sum_{i=1}^n q_ix_i $$ ...
16
votes
2
answers
880
views
Does Karp reducibility yield a total order?
Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?
- 355
13
votes
2
answers
608
views
Does PPAD really capture the notion of finding another unbalanced vertex?
Complexity class PPAD was invented by Christos Papadimitriou in his seminal 1994 paper. The class is designed to capture the complexity of search problems where the existence of a solution is ...
- 546
15
votes
1
answer
471
views
Validity of exponentiation in a polynomial time reduction
I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer.
In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-...
- 1,137
4
votes
0
answers
154
views
Graph Isomorphism Algorithm of Vertex Transistive Graphs and other
What are the best known Graph-Isomorphism algorithms for below graph classes-
1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive.
Are they GI Complete?
...
- 533
1
vote
1
answer
232
views
Complexity of permanent modulo prime
Given $M\in\Bbb Z^{n\times n}$ with $O(n)$ bit entries (could be all in $\{0,1\}$), $p$ a prime of $O(n^\alpha)$ bits for some $\alpha\in(0,1]$ and a $c,d\in\Bbb Z$ with $0\leq c<d<p$, is 'Is $\...
- 12.8k
4
votes
0
answers
188
views
Can coNLogTime verification be used instead of PTime verification when characterising NP?
I recently read a paper that presented a proof calculus where the verification of whether a given proof is valid was NL-complete. The authors apparently decided that the checking procedure was not ...
- 3,033
-3
votes
1
answer
156
views
Could you explain to me the reduction? [closed]
I am looking at the following solved exercise:
I haven't really understood at the reduction the part that we construct for each number $a_i$ a package of measurement $(\frac{4}{A}a_i, 5,3)$. Why do ...
- 95
1
vote
2
answers
267
views
Reduction from independent set in hypergraphs to independent set in graphs
Let me introduce my notations.
IS-H :
Input : an hypergraph $G=(V,H)$, an integer $k$
Question : is there a (weak) independent set of size $k$, i.e. a set $S \subseteq V$ such that $|S| \ge k$ and ...
- 137
3
votes
0
answers
92
views
Maximum weight triangles in dense graphs
There are multiple results (Vassilevska and Williams STOC09, for instance) on computing efficiently minimal-weight triangles (or more generally patterns) in node-weighted graphs.
Several of these ...
- 1,085
13
votes
2
answers
1k
views
Is ALogTime != PH hard to prove (and unknown)?
Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP:
Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on diagonalization ...
- 3,033
7
votes
1
answer
1k
views
On reducing the hardness of CNF-SAT to k-Clique
CNF-SAT refers to the following problem:
Given a boolean formula $\phi$ in conjunctive normal form, does there
exist an assignment to the variables that satisfies $\phi$.
There are several ...
- 5,127
8
votes
1
answer
342
views
Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT
Stated briefly, my question is: is Karp's original proof reducing SAT to 3SAT unnecessarily elaborate? The details are as follows.
In his 1972 paper Reducibility Among Combinatorial Problems, Karp ...
6
votes
1
answer
207
views
Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis
The Berman Hartmanis conjecture which formally states that there is an isomorphism for two $NP$ complete languages $L_{1}$, and $L_{2}$, the isomorphism is a bijective function $f()$ such that $f()$ ...
- 1,181
1
vote
0
answers
122
views
L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph
Recently I read this paper which was published in FOCS2007.
In section 4, just before Theorem 4.2, the author mentioned that the gadget construction of Minimum Dominating Set in UDG is similar to ...
- 11
2
votes
1
answer
450
views
Is there a FNP problem that's NP-hard but not FNP-hard?
For the reductions, choose a class C such that [it's clear what FC means]
and FC is not known to be able to solve the satisfaction search problem,
and assume that FC indeed can't solve that search ...
user6973
5
votes
0
answers
192
views
Is anything known about Sokoban with only 1 box?
This is intended to be a simpler version of my earlier question here.
In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is
the corresponding decision problem, and 1-Sokoban ...
user6973
13
votes
1
answer
3k
views
Improving Cook's generic reduction for Clique to SAT?
I am interested in reducing $k$-Clique to SAT without making the instance much larger.
Clique is in NP so it can be reduced to SAT using logarithmic space.
The straightforward Garey/Johnson textbook ...
- 18.9k
4
votes
1
answer
354
views
Polynomial-time reductions between undecidable languages
The Turing degree $\mathbf{0}'$ is defined as
all languages Turing-equivalent to the halting problem.
In fact any recursively enumerable language is
polynomial-time reducible to the halting problem.
...
- 284
12
votes
1
answer
291
views
Slowest many-one reduction?
When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. ...
- 11.3k
15
votes
1
answer
523
views
Sampling a uniformly random satisfying assignment
Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists).
Clearly ...
- 2,803
5
votes
1
answer
112
views
NP-Complete Convergent Reductions?
A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the ...
- 2,786