Questions tagged [np]

Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
11