Questions tagged [polynomial-time-reductions]
Used in questions asking for efficient (polynomial-time) reductions between computational problems.
175 questions
1
vote
0
answers
34
views
Are all known NP-complete problems known to be p-isomorphic?
I am currently looking into Berman-Hartmanis Conjecture. [Paper 1, Wiki]
In the abstract of Paper 1, it is mentioned that all the known problems are p-isomorphic. (Paper was published in 1975.) The ...
- 219
1
vote
1
answer
186
views
Polynomial hierarchy, many-one reduction, but with co-NP subroutine
Let's say I have three problems, problem A is $\Sigma_{2}^{P}$-complete, problem B is co-NP-complete and problem C $\in \Sigma_{2}^{P}$.
In a many-one reduction from A to C (i.e. showing hardness for ...
- 13
0
votes
0
answers
20
views
How to transfer Hamilton cycle problem in non-directed graph to zero-one equation?
There are many discussions showing how to reduce Zero-One Equation problem to Hamilton cycle problem in a non-directed graph. However, none of these shows opposite transferring. I need to find a ...
0
votes
0
answers
39
views
Reduction from satisfiability to independent set in maximum variation
Main question is: I want to do reduction:
$$\text{MAX-3SAT}\leq_p\text{MAX-INDSET}.$$
My tried so far:
But I know the reduction $\text{3SAT}\leq_p\text{Independent Set}.$
Input: Given a 3CNF formula $...
- 97
0
votes
1
answer
132
views
Satisfiability to graph isomorphism reduction
$\text{GI} = \{\langle A, B \rangle∶ \text{ graph A is isomorphic to graph B} \}$
I want to reduce from, $\text{3SAT}\leq_p \text{GI}.$
I know how to reduce from GI to SAT: Whenever we see two ...
- 33
2
votes
1
answer
117
views
NP reducibility proof steps
Can someone help me to verify my understanding of reducible NP problems?
Look at this tree:
The root shows the most complex NP complete problem. So, given that circuit-sat is NP complete, by this ...
- 109
1
vote
1
answer
93
views
$SET-COVER\leq_pIP$
Let:
$IP=\left \{ \left \langle A,b \right \rangle \right \}:$ $A$ is a $m\times l$ matrix over the integers, $b$ is a vector of $m$ integers and there exists a vector $x$ of $l$ integers s.t $Ax\geq ...
- 341
0
votes
1
answer
100
views
Ways to prove a problem is hard for a class
If I want to prove that some language $A$ is hard for class $C$, the obvious way is a Karp reduction. You could also show it by finding some subset of $A$ that's hard for $C$.
What other ways are ...
- 23
2
votes
1
answer
121
views
About complexity of Polynomial time (Karp) reduction
[Resource/information request]
I would like to know if, in literature, there exist two languages $L_1$ and $L_2 \in NP$-complete set such that reducing $L_1$ to $L_2$ amounts to solving an instance of ...
- 219
1
vote
1
answer
114
views
3SUM Reduction to Distinct Pairwise Sum
The 3SUM problem is defined as follows:
Given three sets of integers $A,B,C \subseteq \{-W,\ldots,W\}$ for $W = n^3$, each containing $n$
integers, determine whether there exsists some $a \in A, b \in ...
- 13
-1
votes
1
answer
73
views
Deducing if a language is in $R \setminus P, P$ or $\notin R$
Let $A \in P$, and some language $B$. We have $f:\{0,1\}^{*}\to\{0,1\}^{*}$ s.t $\forall x \in \{0,1\}^{*}$ we have: $x \in B \iff f(x) \in A$.
In addition we know that there exists a family of cycles ...
- 189
0
votes
1
answer
110
views
Is it possible there exists a reduction that satisfies conditions of reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}?$
I am following the Barak and Arora book. I have asked this question regarding reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}.$
Is it possible to show that there exists a reduction that satisfies ...
user172436
1
vote
1
answer
116
views
Reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}$
I am following the Barak and Arora book, in circuit chapter, they use direct reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}$ directly without any clue.
How to construct an explicit reduction ...
user172436
2
votes
1
answer
218
views
Polynomial time reductions in DTIME
A class $∁$ is closed under polynomial time reductions if for every two languages $L_1, L_2$
such that $L_1 \leq_p L_2$ and $L_2 \in ∁$, it holds that $L_1 \in ∁.$
How to Show that for every $𝐿_1 ∈ \...
user150715
1
vote
1
answer
126
views
If $𝐵 ∈ \text{PSPACE},$ then $𝐴 ∈ \text{PSPACE}.$
We say that a language $𝐴$ has a probabilistic-poly-time reduction $𝑓$ to a language $𝐵$ if:
There exists a probabilistic polynomial time TM computing the (randomized) function $𝑓.$ Note that $𝑀(...
user172436