Skip to main content

Questions tagged [polynomial-time-reductions]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

If A ∈ coNP, B ∈ NP and $NP \neq coNP$, is it possible to Karp reduce A to B?

If A $\geq_p$B and $B\in NP$, $A\in coNP$, then we can build a Turing machine $M_A$ using $M_B$ machine of B. Input: w We make a new word with a reduction function $f(w)$. Then we run $M_B$ on $f(w)$ ...
Naneless's user avatar
1 vote
1 answer
45 views

Reducing the Independent Set Problem to Independent Set for 3-Colorable Graphs

I am exploring a reduction from the general Independent Set Problem to the Independent Set Problem specifically for 3-colorable graphs. The goal is to demonstrate that the maximal independent set of a ...
Ferran Gonzalez's user avatar
0 votes
2 answers
22 views

K-Assignment Search to Decision

Given a set of variables X, and a set of subsets of these variables, each set of size k (each subset includes exactly k variables), we would like to find an assignment 1...k to each variable such that ...
Avi Tal's user avatar
  • 339
4 votes
1 answer
216 views

Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

As the title states, I need to prove that the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard. I'm not looking for a solution but a clue or something to help me ...
OE.omergunr100's user avatar
1 vote
1 answer
65 views

NP, NP-Hard and NP-Complete

If a problem S is NP-Complete and we know that a problem Q is polynomial time reducible to S. Does that mean that Q belongs to NP? Also, when can we state that Q is NP-Hard but does not belong to NP? ...
Shreyas Shrawage's user avatar
4 votes
0 answers
38 views

Cardinalities in set coverings

Let $I$ be a set of items; $C \subseteq \mathcal{P}(I)$ be a set of subsets of $I$, where $\mathcal{P}(I)$ stands for the power set of $I$; And $C(i) = \{ c \in C \mid i \in c \}$ be the set of sets, ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
54 views

Why does this approach not work on the SubSet Sum Problem?

I was reading this post, and in it I learned how to make difficult instances of the SubSet Sum Problem. There the guy who responded to the post says that it is necessary to have density 1.0 and all ...
Edu's user avatar
  • 1
1 vote
1 answer
44 views

Is it possible to find reductions from problems in $\mathsf{NP}$ to SAT based solely on the certificate verification algorithm?

The following problem has made me ask this question: Given a boolean formula $\varphi(X)$ decide if there exists a quantification of $\varphi(X)$ with $k$ $\forall$ quantifiers that holds true. ...
rus9384's user avatar
  • 1,684
2 votes
1 answer
125 views

Problem about $NP \neq coNP$

I need to show that assuming $NP \neq coNP$ then there are 2 non-trivial languages $A$ and $B$ ($A,B \neq \emptyset, \Sigma^*$) in $NP \cup coNP$ such that there's no polynomial time reduction from A ...
Yarin's user avatar
  • 275
1 vote
1 answer
78 views

Reduction from dominating set to disconnected dominating set

Consider an undirected graph $G = \langle V, E\rangle$, and a set $S\subseteq V$ of vertices. We say that $S$ is a dominating set, if for every vertex $v\in V$, it holds that $v\in S$, or $v$ has a ...
Zumikya's user avatar
  • 73
1 vote
1 answer
122 views

How to construct complement of NFA universality?

Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal? I tried to use the fact that NFA-universality is PSPACE-...
NooneAtAll3's user avatar
1 vote
0 answers
35 views

Reduction from Hamiltonian path to Tripartite decision problem

I teach a fairly advanced algorithms class to high schoolers and I accidentally presented them with a bunk reduction from Hamiltonian path to the Tripartite graph decision problem. My attempt involved ...
bbg07's user avatar
  • 11
0 votes
0 answers
51 views

HAMILTONIAN PATH AND SUBSETSUM

If we were to discover a deterministic algorithm capable of deciding, in polynomial time, whether a given graph contains a Hamiltonian path, would that imply that the problem SUBSETSUM belongs to P? ...
Drat's user avatar
  • 1
-1 votes
1 answer
41 views

Choose elements from sets that form a permutation: NP hard?

Let $n$ be a positive integer and $[n] := \{1,2,3,...,n\}$. You are given $k$ non-empty subsets of $[n]$. Decide whether it is possible to select exactly one element from each subset such that the ...
Muses_China's user avatar
0 votes
0 answers
44 views

Reduction from novel problem to Set Cover

i would like to perform a reduction for my novel problem to preferably the set cover problem, but i am a bit lost.. My problem can be described as follows: Suppose you have given an binary word as ...
Sven Fiergolla's user avatar
3 votes
1 answer
63 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{...
Zee's user avatar
  • 243
1 vote
0 answers
35 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 ...
Soroush Vahidi's user avatar
0 votes
0 answers
39 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 ...
Yavuz Bozkurt's user avatar
1 vote
1 answer
83 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$,...
Soroush Vahidi's user avatar
0 votes
1 answer
46 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 ...
nicoyanovsky's user avatar
2 votes
1 answer
129 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, ...
Hughson's user avatar
  • 21
0 votes
2 answers
71 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 $...
Pratik Hadawale's user avatar
2 votes
1 answer
64 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 ...
Ank i zle's user avatar
  • 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 ...
Loic Stoic's user avatar
1 vote
0 answers
134 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 ...
Soroush Vahidi's user avatar
2 votes
1 answer
42 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 ...
Jonas Juul Hansen's user avatar
0 votes
1 answer
56 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)...
NL1992's user avatar
  • 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 ...
Soroush Vahidi's user avatar
0 votes
1 answer
208 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 ...
Soroush Vahidi's user avatar
1 vote
1 answer
21 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(\...
advocateofnone's user avatar
1 vote
1 answer
98 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 $...
obolenskaya00's user avatar
1 vote
1 answer
33 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),\...
Felix's user avatar
  • 161
1 vote
1 answer
195 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 ...
kim120's user avatar
  • 21
1 vote
1 answer
36 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 ...
Balchandar Reddy's user avatar
0 votes
0 answers
52 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$, ...
Keio203's user avatar
  • 257
0 votes
0 answers
52 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 ...
Robin Kurtz's user avatar
0 votes
0 answers
224 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 : ...
Emily's user avatar
  • 1
1 vote
1 answer
944 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 ...
False Equivalence's user avatar
0 votes
0 answers
259 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 ...
Farewell Stack Exchange's user avatar
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 $...
Lázaro Albuquerque's user avatar
3 votes
1 answer
98 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 ...
Subhankar Ghosal's user avatar
0 votes
1 answer
455 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 ...
Sp Jan's user avatar
  • 11
0 votes
0 answers
201 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. ...
Prboetic's user avatar
2 votes
1 answer
211 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 ...
Tom Finet's user avatar
  • 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 ...
Nadav Shani's user avatar
1 vote
0 answers
32 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-...
Albert Hendriks's user avatar
1 vote
1 answer
80 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})$...
Algebruh's user avatar
  • 321
1 vote
1 answer
146 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 ...
Francis's user avatar
  • 65
1 vote
1 answer
856 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 ...
entechnic's user avatar
  • 143
1 vote
1 answer
267 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 $...
entechnic's user avatar
  • 143