Questions tagged [polynomial-time-reductions]
Used in questions asking for efficient (polynomial-time) reductions between computational problems.
137
questions
3
votes
1
answer
24
views
EXP reduction to show NEXP-completeness
I wonder why can't I allow an exponential-time reduction from all problems in $\textbf{NEXP}$ to a language $L$ and claim $L$ to be $\text{NEXP-complete}$.
The computational complexity class $\text{...
1
vote
0
answers
19
views
Scheduling jobs with the same release time and different due dates on a single machine
Consider the problem of scheduling jobs with different lengths on a single machine while the jobs have the same release times and different due dates. The goal is to schedule the maximum number of ...
0
votes
0
answers
21
views
How to prove Set-Cover problem is NP hard via reduction from Clique problem?
Since I know that the reduction Clique $\leq_{p}$ Vertex-Cover and Vertex-Cover $\leq_{p}$ Set-Cover are possible, I know how to show this using transitivity property of reductions. However is there ...
0
votes
1
answer
26
views
Bipartite matching with constraints on one part
We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
0
votes
1
answer
32
views
Let 3-COL-$K_4$-FREE be the decision problem that asks if a graph that doesn't contain $K_4$ admits a 3-coloring. Show that the problem is NP-complete
I'm kind of struggling with this excercise. The obvious thing to try is to show that 3-COL $\leq_p$ 3-COL-$K_4$-FREE
($\leq_p$ stands for polynomial reduction). It is clear that 3-COL-$K_4$-FREE is in ...
- 15
2
votes
1
answer
67
views
How to provide a reduction from 3SAT to domatic number problem
How to provide a reduction from 3SAT to domatic number problem.
Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V $ into at least k disjoint sets of vertices, ...
- 21
0
votes
0
answers
14
views
Analogue of NP for oracle problems
I was just reading this question on the quantum computation stack exchange. It asks whether the HSP is in NP or not, and the answer notes that NP is a class of languages, not oracle problems.
The ...
- 265
0
votes
2
answers
36
views
How can a $P(n)$ run in polynomial time if it calls $R(m)$ which has exponential time
We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in n. Unfortunately, a significant flaw was discovered in $Q(m)$, and it had to be replaced by $...
- 305
2
votes
1
answer
59
views
Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$
I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
- 153
0
votes
0
answers
34
views
Reduction between problems where problem A solves problem B with probability $\frac{2}{3}$
Suppose we have a problem, $A$, and a machine $T_A$ that solves $A$.
Now, let's say we have a problem $B$ that is solvable with a polynomial number of calls to $T_A$, and we call $T_B$ the machine ...
- 203
0
votes
0
answers
96
views
Does there exist an FPTAS for bin packing problem?
We know that there does not exist an FPTAS for the bin packing problem because it is a strongly NP-HARD problem, as the 3-partitioning problem which is strongly np-hard, can be reduced to the bin ...
2
votes
1
answer
29
views
Partition a family of sets to maximize cumulative overlap and cardinality
My problem is this: I have a list of $n$ items $N$ (think of them as the natural numbers $1,\dots,n$) and $m$ subsets of $N$ $S_1,\dots,S_m$ which may overlap. The objective is to find a partition of ...
0
votes
1
answer
32
views
Polynomially many instances imply a polynomial reduction?
I have a language $L$ which is NP-hard and I have another language $L_1$, s.t. if I take an instance $q$ of the decision problem corresponding to $L$, and if one of polynomially many instances, $f_1(q)...
- 103
0
votes
0
answers
53
views
Is this minimizing problem NP-hard?
We have $c$ arrays of positive integers, named $j[1],j[2],j[3]..,j[c]$. We know that the length of $j[i]$ is $c-i+1$. In addition, the sum of the numbers of $j[i]$ is greater than or equal to the sum ...
0
votes
1
answer
162
views
Is this sorting problem NP-complete?
Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease ...
1
vote
1
answer
19
views
Are the indices of variables in the formula variable?
Let $L$ be an arbitrary language in $\Sigma_3$. Thus it can be written that $x \in L \Leftrightarrow \exists y^{p(|x|)} \forall z^{p(|x|)} \exists w^{p(|x|)} \langle x,y,z,w \rangle \in B$ where $p(\...
- 2,933
1
vote
1
answer
39
views
union of NP and co-NP, closure under polynomial time reduction
Is $Union = NP\cup co-NP$ closed under polynomial-time many-one reductions?
I understand that in order to be so, for $A\in Union, A \leq_P B $ there should exist a polynomial time computable function $...
1
vote
1
answer
30
views
Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning
I'm currently stuck showing $NP$-hardness of a problem of mine.
An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following:
Given a set of tupels $B=\{(b_1,1),\...
- 161
1
vote
1
answer
175
views
Show problem is NP-hard
I'm preparing for my exam and I got stuck on the following problem:
The gardening problem:
We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is ...
- 21
1
vote
1
answer
31
views
Choosing the ideal problem to prove the hardness
I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from ...
- 162
0
votes
0
answers
31
views
Question about unary languages
Let $A$ be any unary language. Prove that if $A$ is NP-complete, then P=NP.
Approach 1: We just have to prove that we can decide $A$ in polynomial time. Consider a Turing machine that on input $w$, ...
- 257
0
votes
0
answers
51
views
I would not be able to get my simulation in my life time
I am running a simulation on my computer. I tried to multiply two polynomials $g(x), h(x)\in GF(2)[x]$, with $degree(g(x))= 8165$, and $degree(h(x))=25$. This multiplication took almost $20$ minutes ...
- 101
0
votes
0
answers
112
views
Polynomial Reduction from 3SAT
Given an undirected graph $G=(V,E)$ where $V$ is a set of vertices, and $E$ is a set of edges and
given a set $D$ where $D \subseteq V $ and $ \forall v \in V \setminus D \: \mid \: \exists w \in D : ...
- 1
1
vote
1
answer
424
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 ...
0
votes
0
answers
166
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
40
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
75
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 ...
- 298
0
votes
1
answer
298
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
118
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
119
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 ...
- 258
0
votes
0
answers
32
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
24
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,469
1
vote
1
answer
65
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})$...
- 301
1
vote
1
answer
119
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
741
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 ...
- 143
1
vote
1
answer
186
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 $...
- 143
2
votes
0
answers
76
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 $\...
- 494
0
votes
0
answers
37
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
106
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$. ...
- 229
0
votes
0
answers
46
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
28
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(...
- 13
1
vote
2
answers
155
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
105
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
16
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 ...
- 123
0
votes
1
answer
86
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
36
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 ...
- 49
0
votes
0
answers
58
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 ...
- 49
-5
votes
1
answer
104
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
102
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
194
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, ...
