Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
520
questions
0
votes
2answers
16 views
Proof of Co-Problem being in NP if Problem is in NP using negated output
Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof?
Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is ...
1
vote
0answers
19 views
Buckets of Water Problem - Part 2
Continuing from this question:
The buckets of water problem
(All the definitions can be found there, so I will not repeat them).
As seen there by Yuval's answer, the problem is NP-Hard.
I was ...
2
votes
1answer
170 views
Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset
I am working on a problem defined as the following
Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our ...
0
votes
1answer
27 views
Does P not NP imply NP COMPLETE disjoint from RP?
According to Wikipedia https://en.wikipedia.org/wiki/RP_(complexity), $P \ne NP$ implies that $RP$ is a strict subset of $NP$. Does anybody have a reference?
Furthermore, am I correct that if this ...
0
votes
1answer
17 views
complexity of dividing set of number with constraints
I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem.
There is a set of $n$ positive ...
0
votes
1answer
24 views
Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$
I'm having a small issue with wikipedia's proof that $RP \subseteq NP$:
An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic ...
0
votes
1answer
68 views
“Given an algorithm, decide whether it runs in polynomial time” is this problem in NP?
This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?).
However,...
-1
votes
1answer
29 views
How to prove P = NP if problem Ī Ļµ NP-complete and Problem complement Ī c Ļµ NP?
How to prove if P = NP if problem Ī Ļµ NP-complete and Problem complement Ī c Ļµ NP?
OR
P = NP if NPC intersects with Co-NPC
0
votes
1answer
8 views
Why is the hitting set problem in NP
I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979):
INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$.
QUESTION: Does $S$ contains a ...
0
votes
0answers
16 views
Given L1 and L2 in NP, if L1 transforms L2 and L2 transforms HC then L1 NP complete?
Why this Question is False ?
NP-complete problems are the hardest problems in NP.
if L is in NP-complete then [L must be in NP, all problems in NP can be transformed to L].
Does this mean that L2 ...
3
votes
1answer
45 views
Complete resolution rule for 1-in-k SAT
In CNF SAT, each clause (A or B or C or...) must contain at least one true literal. The resolution rule applies to pair of clauses who have exactly one opposite literal.
(A or B or C) and (!A or D ...
0
votes
0answers
18 views
how to prove that $NP \cap co - NP$ = { S | S such that there exist a Strong Deciding Algorithm for S}?
i need to prove that and i find it struggle:
given:
for deciding problem S:
a non deterministic algorithm $A(x)$ is strong deciding algorithm if:
$x \in S =>$ fo every run of $A(x)$ returns "Yes"...
0
votes
0answers
103 views
Exact2IS - Question
I have the following question for Exact2IS problem that is defined:
$$ \mathrm{Exact2IS} = \{(G,k) \mid \text{$G$ contains exactly two independent sets of size $k$}\}. $$
and I would like to know ...
2
votes
1answer
127 views
Combining 2 problems in NP into one
Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$.
Can S be solved with oracle access to only one problem in $NP$?
...
0
votes
3answers
40 views
Is it possible that Co-NP = P but NP != P
Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (...
4
votes
2answers
483 views
Can 3-coloring be reduced to 3-clique?
I'm a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I'm ...
3
votes
1answer
85 views
Having trouble understanding a proof of Mahaneyās theorem
I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.
I am not sure why $aā$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $aā$ cannot be in between $...
0
votes
1answer
53 views
Polynomial-time reduction of Primality and 3-SAT
Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.
Thank you.
1
vote
1answer
46 views
Reducing independent set to triangle-free subgraph
The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$.
An instance of the TFS (...
0
votes
1answer
27 views
Maximum number of positive literals in 2SAT
MAX 2SAT is NP complete.
Instead of satisfying the maximum number of clauses, I have a fully satisfiable 2SAT formula and I want to have the maximum number of positive literals in the assignment (...
0
votes
0answers
26 views
How can I prove that the high-degree independent set problem is NP-hard?
I'm learning about NP Completeness, and I have come across the following problem
The decision-version of the high-degree independent set (henceforth "HDIS") problem is stated as follows: Given a ...
1
vote
1answer
57 views
P=NP when number of inputs that give 1 is bounded by polynomial
Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, ...
0
votes
0answers
18 views
the correctness of 2-satisfiability problem algorithm by using implication graph
I learned finding a solution of 2-sat problem algorithm below.
The point are below
(1) when constructing the implication graph
(2) finding there is no occurrence of a variable x and its negation x' ...
2
votes
0answers
25 views
Names of specific SAT variants
I enjoy reading research on satisfiability, but sometimes it's easier to find relevant information when you know the names of the variants.
Example:
All the clauses are width 3 and must have ...
1
vote
2answers
68 views
Are NP proofs limited to polynomial length?
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, ...
0
votes
0answers
27 views
Design of a single-tape NTM solving the TSP in $O({n}^4)$ time at most
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman, Motwani where I came across a claim that a "single-tape NTM can ...
1
vote
0answers
52 views
CircuitSAT to 1-in-3SAT
This question follows
Unique 3SAT to Unique 1-in-3SAT
Consider an AND gate such that (A ā§ B) = C. It can be trivially expressed in 3SAT with 4 clauses and no extra variables.
$$
(A āØ B āØ \overline{...
1
vote
0answers
27 views
How to the NP hard of a problem that search for a subset of points with maximum scores?
Suppose in a plane, there is a set of points, whose distance to $(0,0)$ is always 1:
$[(0,1),(1,0),(0.707,0.707),(0.707,-0.707),...]$
Each point is assigned with a weight (possible negative):
$[w(...
0
votes
0answers
188 views
Witness finders
Given an NP language $L$, let a witness-finder for $L$ be a polynomial-time algorithm $M$ that
actually outputs a yes-witness $y$ for $x$ whenever $x \in L$, but could behave arbitrarily if $x \notin ...
2
votes
2answers
148 views
Unique 3SAT to Unique 1-in-3SAT
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.
It was made from a binary multiplication circuit where I multiplied two primes numbers A and B such ...
1
vote
1answer
26 views
Unique 1-in-3 SAT
Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.
I know the value of each bit of the unique assignment because it was made from a binary ...
1
vote
1answer
41 views
Karp reduction from optimization problems to decision problems
When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other.
Focusing on Cook reductions, there exists a natural Karp ...
1
vote
1answer
26 views
One-way function is not injective when it is in NP
Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \...
1
vote
1answer
37 views
Independent set poly reducible to Strongly independent set?
A strongly independent set of a graph $G'$ is a subset $S$ of vertices such that the distance in $G'$ between every two distinct vertices in $S$ is larger than $2$.
It is possible to reduce an ...
0
votes
2answers
62 views
Is P contained in NP-hard?
I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me.
NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained ...
0
votes
1answer
39 views
If a problem is complete for NP, is its complement complete for co-NP?
I am trying to prove that for a NP problem that is complete, its complement co-NP should be complete as well.
We know that a decision problem A $\in$ NP-complete if a) it is in NP and b) if every ...
3
votes
3answers
129 views
Has anyone seen a NP graph problem like this before?
I have a following graph-based problem:
Input: positive integers K and L, undirected graph G
I have to choose K vertices from this graph
In the path between each pair of chosen K vertices there ...
2
votes
1answer
235 views
Understanding definition of NP and co-NP
From some of the texts I read, one definition of NP is: "An equivalent definition of NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." and that we ...
3
votes
1answer
28 views
How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages
I think this is a basic topic in complexity, but I would like to ask how to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages. From the definition of my textbook, $$co-\mathcal{L}...
2
votes
1answer
18 views
symmetrical subtraction between $L_1 \in \mathsf{P}$ and $L_2 \in \mathsf{NPC}$
If $L_1 \in \mathsf{P}$ and $L_2 \in \mathsf{NP-Complete}$ and $L_3$ is the symmetric difference between $L_1$ and $L_2$, is $L_3$ also in $\mathsf{NP-Complete}$ necessarily?
I'm pretty sure the ...
2
votes
1answer
33 views
Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?
Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following:...
1
vote
2answers
86 views
Proving NP-completeness of a surveilled graph problem
So suppose I have a graph consisting of a tuple $(V,E,A,g)$ where $V$ denotes vertices, $E$ denotes edges, $A$ denotes a subset of $V$ (i.e. $A \subseteq V$), and $g:A\rightarrow\mathbb{N}$ is a ...
0
votes
0answers
40 views
Isn't every polynomial time problem an NP problem?
See here. Knapsack problem -- NP-complete despite dynamic programming solution?
The only reason Knapsack problem is NP-complete is because input comes as binary numbers so n is actually 2^n. Since ...
1
vote
1answer
73 views
Prove a TM problem is NP-complete
Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$
This question looks weird to me ...
0
votes
1answer
27 views
If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?
Deciding bipartite hypergraph coloring is NP-hard:
While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-...
2
votes
1answer
30 views
Is a DTM with k-tapes not the same thing as a NDTM with k-branches?
In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use.
If a language L is ...
0
votes
1answer
106 views
Show that NPā©coNP =ā
I know that P is a subset of NP, but I'm not sure what this tells me about P as it relates to coNP?
I feel like this is how I should go about proving it, but I'm not sure how. Otherwise, I could find ...
23
votes
4answers
4k views
Assuming P = NP, how would one solve the graph coloring problem in polynomial time?
Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?
Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for ...
5
votes
1answer
55 views
Is there such a notion as “effectively computable reductions” or would this be not useful
Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by ...
2
votes
1answer
42 views
Clarifiaction on the NP-hardness of k-SUM-variants
I am currently looking into the $k$-Sum Problem and some of its variants. However i stumbled onto an inconsistency, that i can not seem to fix.
If we begin with $3$-Sum, the 'textbook'-definition ...
