Questions tagged [polynomial-time-reductions]
Used in questions asking for efficient (polynomial-time) reductions between computational problems.
118
questions
-4
votes
0
answers
72
views
2-Satisfiability is NP Complete, isn't it?
To show that any formal language is NP Complete first it must be showed that this formal language is both in NP and NP Hard.
So to show that 2-Satisfiability is NP Complete first it must be showed ...
1
vote
1
answer
38
views
If every NP-hard language is PSPACE-hard then NP=PSPACE
To prove PSAPCE = NP we will show following inclusions :
NP $\subseteq$ PSPACE : If every NP-hard language is PSPACE-hard then
SAT is also PSPACE-hard. Since every language in PSPACE can be
reduced ...
- 173
0
votes
0
answers
62
views
Horn Satisfiability is NP Complete, isn't it?
To show that any formal language is NP Complete first it must be showed that this formal language is both in NP and NP Hard.
So to show that Horn Satisfiability is NP Complete first it must be showed ...
0
votes
1
answer
39
views
Reducing to an NP-complete problem
If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$?
I think we should be able to say that $R$ is in NP since an instance of $...
3
votes
1
answer
44
views
Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?
Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$?
A ...
- 180
0
votes
0
answers
12
views
Np polynomial reduction
There is a theorem that states if $(B∈NP)$ and $(A\propto B)$, then $(A∈NP)$, then what if ($A∈NP$) and $(A\propto B)$, does it means that $(B∈NP)$?
($\propto$ being a polynomial many-one reduction)
- 1
0
votes
1
answer
64
views
If you can reduce A to B, does that mean B reduces to A?
If you can reduce A to B, does that mean B reduces to A?
Sorry for the stupid question. I think the answer should be yes, because if you can convert all yes-instances of A to yes-instances of B, then ...
0
votes
0
answers
44
views
Prove minimum vertex bisection problem is reducible from bisection width, thereby proving NP-Completeness
The bisection width problem gives you a yes or a no -> if there exists a bisection of size at most $K$ for $G=V,E$.
Minimum Vertex Bisection problem gives you a bisection of the smallest size.
...
- 1
2
votes
1
answer
48
views
Reduction from vertex-cover to system of quadratic equations
Define
$$\text{SQE}=\{S\ |\ S\ \text{is a system of quadratic equations with real solutions}\}$$
and
$$\text{VC}=\{G\ |\ G\ \text{is a simple undirected graph with a vertex cover}\ \leq k\}$$
I am ...
- 248
0
votes
0
answers
28
views
computation P=L [duplicate]
i have the following question which I'm having some hard time to solve:
prove: if every two Languages $A$ and $B$ that have a polynomial reduction ($A$ to $B$) also have a log space reduction ($A$ to ...
1
vote
0
answers
15
views
example of an NL-completeness reduction?
I'm looking for simple examples of nondeterministic log-space completeness reductions. In particular I seem unable to construct any nontrivial widget using 2-SAT clauses, which is known to be NL-...
- 2,376
1
vote
1
answer
50
views
Why is $\mathsf{QP}$-hardness impossible?
I found this task in an old exam and couldn't get my head around it:
We define the class of languages $\mathsf{QP}$ as follows: $$\mathsf{QP} = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(2^{\log(n)^k})$...
- 279
1
vote
1
answer
73
views
Why NP-Complete reduction is not reversible?
I have read the question asked here Is polynomial reduction reversible and the logic actually makes sense to me. In other words, if A is polynomially reducible to B, it means that A <= B in terms ...
- 65
1
vote
1
answer
470
views
Show that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete
I want to show that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is also $\mathcal {NP}$-Complete.
Sparse Subgraph problem:
Input: Undirected graph $G(V,E)$, two ...
- 133
0
votes
0
answers
46
views
Show that a problem about permutations is NP-Complete
I want to prove that the following problem is NP-Complete.
Input: Set $S = \{s_1, \dots, s_n \}$, set $T \subset S \times S$, that contains ordered pairs $(s_i, s_j) : s_i \neq s_j$, and an integer $...
- 133
0
votes
0
answers
37
views
Polynomial reduction to SAT with a condition
Let L be in NP.
Is there always a reduction from L to SAT where atleast m-1 clauses (m being the number of clauses in the CNF formula) can be satisfied?
When w is in L it is trivial because the ...
2
votes
0
answers
73
views
Limited number of calling for a decision blackbox to compute all the solutions
I am trying to reduce between a solution problem and a decision version of the same problem.
The problem is the orthogonality problem. Given $2$ sets $L$ and $R$, whose size each is $n$ vectors over $\...
0
votes
0
answers
30
views
Difficulty in finding a counter example for a polynomial reduction
I am doing some exercises on proving NP Complete problems and the first problem was directed bipartite graphs with a Hamiltonian cycle and the second one was undirected bipartite graphs with a ...
- 1
2
votes
1
answer
73
views
Maximum independent subset for graphs with lots of edges
Consider an NP-hard graph problem, like the maximum independent set problem.
Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
- 309
0
votes
0
answers
40
views
In-place Acceptance Problem
In-place Acceptance Problem (InAP)
Instance: A deterministic Turing Machine M and a w input for it.
Question: Does M accept the input w without going through cell (|w|+1)?
Show that InAP is PSPACE-...
1
vote
1
answer
23
views
Can I reduce from the recognition version of one probem to another without knowing the exact parameter?
I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(...
- 11
1
vote
2
answers
88
views
What's wrong with the reduction from integer programming to linear programming?
I'm confused with polynomial-time reduction and NP-hardness.
Let's say that the following integer programming is NP-hard.
$\min_{x \in K} f(x)$, where $K$ is a finite subset of $\mathbb{N}$.
But it is ...
- 113
1
vote
1
answer
55
views
How do I prove that the clique problem is polynomial-time reducible to the odd cycle transversal problem?
I have the following problem:
Let $H=(W, F)$ a graph and $k \in \mathbb{N^*}$ be an instance for problem $\textbf{CMP}$ (i.e. the clique problem). Let $W'$ a set of new vertices, $|W'|=|H|=n$. We ...
- 75
2
votes
1
answer
14
views
Question on worst-to-average-case reductions
Consider two decision problems A and B.
We know that A reduces to B in polynomial time --- if we could solve B, we have a procedure to solve A.
Now, let's say it is known that the worst case instances ...
- 23
0
votes
1
answer
43
views
How can we prove that a reduction exists?
Problem: I have two computational problems, $A$ and $B$. We know that $A \in \texttt{Psearch}$ and I want to prove that $A \leq_p B$ for all problems $B$.
Goal: It is my understanding that my goal is ...
- 1
1
vote
0
answers
26
views
Relationship between complexity classes W[1]-hard and NP-hard?
If i have a parameterized reduction from multicolored independent set (W[$1$]-hard) to some problem $A$, which take polynomial time. Can i say that problem $A$ is NP-hard?
in other words, Is ...
- 53
0
votes
0
answers
41
views
Reduction techniques in complexity
I am learning computational complexity and parameter complexity. In order to proof that a problem is np-hard, we should reduction one which is np-hard to the problem. However, I don't have any idea ...
- 53
-4
votes
1
answer
57
views
Proving correctness of Polynomial reduction
Given a problem A is NP-Hard and A ≤𝑝 B, is there a way to prove that B is also NP-Hard?
- 1
1
vote
1
answer
61
views
A different way of reducing subset sum to partition
For brevity, let $s(D) = \sum_{d\in D} d$ denote the sum of the elements in $D$.
Given a set $A = \{a_1, \dots, a_n\}$ of positive integers, and a target value $K$, the subset sum problem is to ...
- 125
2
votes
2
answers
79
views
Problem reduction: Can YES-Instances also be mapped to NO-Instances if there is perfect correspondence?
Definition: Problem A is reducible to problem B if an algorithm for solving
problem B efficiently (if it existed) could also be used as a
subroutine to solve problem A efficiently. When this is true, ...
0
votes
1
answer
41
views
polynomial time approximation algorithm problem
How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem?
For say we have 2 approximation problems which less than equal 2C*. But when we have a ...
0
votes
1
answer
41
views
Algorithm to reduce a Circuit-SAT to NAND-SAT
I am trying to construct an algorithm to reduce OR, AND and NOT gates into NAND-SAT. Can someone give me a hint as to where to start?
-1
votes
1
answer
30
views
If two languages are polytime reducable, does that imply they are also turing reducable
Is it possible for a pair of languages where A ≤T B but not A ≤p B?
I am not sure if this could be the case since a turning reduction would imply we can use a decider for one language to decide ...
0
votes
1
answer
50
views
Reduction: Does polytime reduction imply Turing reduction?
I am unsure if given $A \leqslant_p B$, does that imply that $A \leqslant_T B$.
If we can polytime reduce $A$ to $B$, that would imply there is a decider for $A$ that runs in polynomial time which can ...
0
votes
1
answer
20
views
Polytime Mapping Reduction from Language A to Language A (identity)
How would I create a polytime mapping reduction to prove A ≤p A for any language A.
I was thinking to assume A is in P to start.
For every 𝑥: 𝑥∈𝐴 iff 𝑓(𝑥)∈𝐴.
But I am not sure what to do from ...
1
vote
0
answers
26
views
Covering Salesman Problem (CSP) polynomial reduction to the TSP
I am facing one problem that consists in polynomially reducing the Coverging Salesmen Problem (CSP) to the Traveling Salesman Problem (TSP).
So, let me first define the CSP. The CSP, I am working on, ...
1
vote
0
answers
23
views
Solve the K_ELEMENT problem using INTERSECT
Suppose you have a machine that takes inputs a set of sets, $\{S_1,S_2,\dots S_n\}$, and an integer $k$. The machine then returns True if $S_1$ intersects every ...
- 293
0
votes
1
answer
42
views
Reduction of np to npc
Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq_p^\mathsf{}A$ then $D$ is $NPC$" is true or not?
My approach: Since $D\leq_p^\mathsf{}A$, therefore $...
- 1
0
votes
1
answer
61
views
Reduction of RE and Rec languages
Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC.
And also I know that if $...
- 1
3
votes
1
answer
79
views
Is there a book with 100 reductions?
In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems.
Question:
I was wondering if there exists something like a database or a book with some ...
- 279
4
votes
1
answer
661
views
Proofs of reduction of any hard problem
Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
- 1
0
votes
1
answer
210
views
If $A\leq_m^\mathsf{}B$ and $B$ is a regular language, does that imply that $A$ is a regular language?
Corollary:1 We know that if $A\leq_m^\mathsf{}B$ and $B$ is decidable then $A$ is also decidable.
This is because if there exists a specific algorithm for solving $B$ and we can also reduce $A$ to $B$ ...
- 1
0
votes
1
answer
79
views
Reduction from undecidability, decidability to decididabilty
If given any two language both
$L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample ...
- 1
1
vote
1
answer
162
views
Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T
Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
- 11
1
vote
1
answer
138
views
Why is Independent Set "at least" and Vertex Cover "at most" k
The decision version of the Independent Set and Vertex Cover problems are phrased as:
Given a graph G and a number k, does G contain an independent set of size at least k?
Given a graph G and a ...
- 113
0
votes
0
answers
69
views
Reduction rules to lower bound minimum degree of a graph
I'm trying to come up with a list of rules that return an equivalent instance to the following problem, while eliminating all vertices of degree 2 or less from the graph:
Given a graph $G=(V,E)$, the ...
- 317
0
votes
0
answers
45
views
Polynomial Reduction from $3SAT$ to $MSAT$
I am supposed to show that
$3SAT$ $\rightarrow$ Every clause hast exact $3$ literals
is polynomial reducible to
$MSAT$ $\rightarrow$ At least half of every clauses' literals are true
Let $F$ be a ...
- 59
1
vote
3
answers
178
views
Spanning tree whose sum of edge weights are between two boundries
I saw this problem:
$\langle G,w,k_1,k_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k_2$ and greater than $k_1$. The problem says that we can prove this ...
- 358
2
votes
3
answers
294
views
Easy proof for $Primes \in NP$
I want to show that $Primes \in NP$ an I've seen multiple proofs that use facts from number theory, like this one.
But isn't it much easier to proof
$$Composites=\{x\in \mathbb{N}\cup\{0\}:x=1 \vee\...
- 147
0
votes
1
answer
38
views
Prove SubsetSum is polyequivalent to SubsetSum with surplus
I'm solving problem 13.17 of What can be computed?, which is asking to prove $\text{SubsetSum} \equiv_{P} \text{SubsetSumWithFives}$.
Here is the definition of SubsetSumWithFives.
SUBSETSUMWITHFIVES: ...
- 27