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
3 votes
1 answer
205 views

NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
1 vote
1 answer
44 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 ...
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 ...
8 votes
2 answers
587 views

NP-hardness for one-dimensional facility location problem with entrance fee for each customer

We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
4 votes
1 answer
215 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 ...
-1 votes
0 answers
24 views

Exercise: More on hashing for estimating sizes of sets

Let m and k be positive integers and let U = Um,k be a 2-wise independent family of hash functions from m bits to k bits. For any fixed set S ⊆ {0, 1} m and a randomly chosen h ∈ U, let I(S, h) be the ...
4 votes
1 answer
138 views

Complexity of a decision problem: system of linear equations over finite field with restricted solutions

I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ ...
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 ...
0 votes
1 answer
160 views

Restriction of SAT to CNF

I have spent a lot of time understanding these two issues. If you can help me, please. Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most twice is solvable in ...
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? ...
1 vote
1 answer
215 views

If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?

If $x \in L$ only if $x \in A$ and $x \in B$, where A is an NP problem and B is a coNP problem, I cannot place $L \in NP$ or $L \in coNP$ without implying that NP = coNP right?
1 vote
1 answer
853 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 ...
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, ...
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 ...
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. ...
2 votes
1 answer
123 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 ...
3 votes
2 answers
164 views

Interpretation of co-NPCompleteness?

Given a Problem $A$ that has an answer $true$ if and only if both conditions $1$ and $2$ are $false$, for some conditions 1 and 2. Whether condition $2$ is $true$ can be tested with certainty in ...
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 ...
1 vote
1 answer
121 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-...
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 ...
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? ...
-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 ...
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 ...
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{...
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 ...
2 votes
1 answer
121 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, ...
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 ...
1 vote
1 answer
81 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
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
207 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 ...
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 ...
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(...
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 $...
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 ...
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 ...
1 vote
0 answers
133 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
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 ...
0 votes
1 answer
54 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)...
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(\...
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 $...
2 votes
1 answer
465 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 ...
1 vote
1 answer
97 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
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),\...
-1 votes
1 answer
152 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 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 ...
0 votes
0 answers
50 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$, ...
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 ...
0 votes
0 answers
223 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 : ...
0 votes
2 answers
636 views

Reduce Subset-Sum to Sat

Is there a reduction from SUBSET-SUM to SAT? Just general SAT, not 3-SAT. Also the given multiset S only has positive integers. SUBSET-SUM is defined as follows: Input: a multiset S = { x1 , ... , xn }...
1 vote
1 answer
941 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 ...