Questions tagged [polynomial-time-reductions]

Used in questions asking for efficient (polynomial-time) reductions between computational problems.

Filter by
Sorted by
Tagged with
-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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
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 ...
user avatar
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)
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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-...
user avatar
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})$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
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 $\...
user avatar
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 ...
user avatar
  • 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$. ...
user avatar
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-...
user avatar
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(...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
-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?
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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?
user avatar
-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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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\...
user avatar
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: ...
user avatar