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
1answer
18 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
20 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
85 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
48 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
36 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 ...
2
votes
0answers
21 views

Flip Output of SAT problem [duplicate]

Why cant I Just create a TM A that runs a NTM B with a formula to compute the SAT Problem and Just Flip its Output. So when the Input NTM B Returns true (formula is satisfyable) the TM A Return false.
0
votes
2answers
33 views

Is there a language which has a polynomial length certificate but not known to have a polynomial time verifier?

The question came to my mind while studying the NP definition. Do we know any such languages?
-1
votes
1answer
58 views

Are there any NP-hard problems for which the following statement is true:

$\overline{A} \le A\ and $ $A \le \overline{A}$ Is the following proof correct? If $\overline{A} \le A \Rightarrow \overline{A} \in NP$ since A is NP-hard $ \Rightarrow A \in coNP$ Since $\...
2
votes
1answer
55 views

NP-completeness of a problem with pretty fast algorithm

Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?
0
votes
1answer
26 views

NP-Complete reductionTrue/False question explanation

Why is the above statement true? my understanding is: (1)3SAT reduces to X implies X is NP-complete or harder. (2)Set Cover reduces to X implies X is neither NP-Complete nor harder. This ...
1
vote
1answer
67 views

An NP-hard problem reduces to its complement?

I found this statement in a true/false test section: Could someone explain in laymans why this is a true statement? My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
0
votes
2answers
147 views

What is wrong with the following $P$ problem?

Our teacher gave us the following statement and we were wondering what is wrong with it. Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$, we cannot check ...
2
votes
1answer
63 views

Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

I am taking a complexity class now, and I struggle to understand the concept of "hardness": Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \...
1
vote
1answer
2k views

A problem in NP but not NP-complete?

Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
0
votes
0answers
21 views

Problem in NP: $EQ1 = \{(p_1,…,p_n): \exists x_1,…,x_m\in Z \ p_1(x_1,…,x_m)=…=p_n(x_1,…,x_m)=0. \}$

I have to following problem to show is in NP class. $EQ1 = \{(p_1,...,p_n): \exists x_1,...,x_m\in Z \ p_1(x_1,...,x_m)=...=p_n(x_1,...,x_m)=0. \}$ Here $p_1,...,p_n$ are polynomials in m ...
2
votes
1answer
73 views

Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)

I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time ...
1
vote
1answer
49 views

How to know if a problem belongs to NP Class?

What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
3
votes
1answer
144 views

Union of a language in P and a language in NP\P

TRUE or FALSE Statement: Assume that $P \neq NP$. Then, for all languages $L_1$ and $L_2$, if $L_1$ is in P and $L_2$ is in NP but not in P then $L_1 \cup L_2$ is in NP but not in P. I have a ...
2
votes
1answer
276 views

O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?

I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list: Initialize an array of integers "colors" with V elements being 1 Using ...
3
votes
3answers
163 views

You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?

My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover ...
0
votes
0answers
18 views

Proving a problem is NP [duplicate]

I've seen in many textbooks if say we have a problem $Q$, we write a non-deterministic algorithm in polynomial time to solve problem $Q$, and then from that point it results that $Q\in NP$. Why is ...
1
vote
1answer
82 views

How to prove Shortest Common Superstring is NP-Hard

After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting ...
0
votes
1answer
80 views

P Vs NP can never be proven one way or the other!

Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem. And since if we prove that any problem in NP is a P that would mean that we have NP=P. ...
0
votes
0answers
61 views

If any problem in NP is not in P then NP C ∩ P = ∅

If any problem in NP is not in P then NPC ∩ P = ∅ The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction. I have not clear ...
2
votes
1answer
22 views

Finding maximal cardinal independent set given oracle

The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the ...
-1
votes
1answer
34 views

Another Subset sum problem

Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
1
vote
1answer
78 views

Subset sum to 0/1 knapsack

How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
0
votes
1answer
39 views

Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it

Is there any known polynomial time algorithm to solve a problem which that problem is in NP. I was told is False but can't think of any counter example now.
5
votes
1answer
147 views

Using decision oracle to solve optimization problem of maximum polyomino tiling

So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of ...
2
votes
1answer
73 views

If A and B are NP-complete, then A ∪ B need not be NP-complete

I am studying the proof of this exercise (link) There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example: $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$ $B =...
1
vote
1answer
560 views

How to prove graph isomorphism is NP?

I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.
0
votes
2answers
51 views

Decide whether an $n$-bit positive integer is composite

Question: Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP? I know that for every composite number, a factor of the number is a ...
1
vote
1answer
23 views

Is there any importance in problems whose witness for membership in a set, cannot be bounded by a polynomial?

The class NP can be defined as a polynomially bounded relation $R$. Where $x \in R$ if there exists some $y$ that has length bounded by $p(|x|)$, where $p$ is some polynomial. Why do we not study the ...
0
votes
0answers
45 views

Which is the most similar NP classic problem, if any exists, to this one?

Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the ...
0
votes
0answers
22 views

NP problem solving

Prove that every NP problem is solvable in $O(2^{n^{k}})$ where $k$ is constant. My approach was that, let's look at the 3-SAT problem. We can solve it by bruteforce in $O(2^n)$, where $n$ is ...
0
votes
0answers
42 views

Confusion about P versus NP [duplicate]

I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
-2
votes
2answers
85 views

Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?

I claim to have solved the travelling salesman problem as follows. (You will have to be familiar with djikstra's algorithm for this.) 1) I am about to start using djikstra's algorithm on any given ...
1
vote
2answers
214 views

P/NP - Polynomial Reduction vs Certificate

I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate. How I understand polynomial reduction is that you can use it to ...
0
votes
2answers
51 views

An example of a computable problem that is not in P

I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set ...
1
vote
1answer
90 views

if $L \in NP$ then its mapping reducible to HALT?

This is true because every language in $NP$ is decidable and therefore HALTS but how do I formally show this?
1
vote
1answer
78 views

How can i prove that MAX-CUT is in NP?

How can i show/explain/prove that Max-Cut is in NP? "For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as ...
5
votes
2answers
2k views

is FIND WORDS in P?

FIND WORDS is the following decision problem: Given a list of words L and a Matrix M, are all words in L also in M? The words in M can be written up to down, down to up, left to right, right to left,...
2
votes
1answer
138 views

If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?

According to this source, If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to ...
2
votes
1answer
106 views

Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G

In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following: Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving ...
0
votes
0answers
45 views

Intersection of decision problems?

Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
8
votes
3answers
482 views

Simple interepretation problem regarding Polynomial Hierarchy?

So $NP$ stands for problems where we have small verifiable witnesses for $YES$ instances and $coNP$ for small verifiable witnesses for $NO$ instances. How does this work for $P^{NP}$ $NP^{NP}$ $coNP^...
1
vote
2answers
75 views

Is the certificate for primality testing polynomial in the length of the input?

If we were to assume that primality testing was in NP. What would the certificate be, so that a polynomial time verifier can check the number X is indeed prime?
0
votes
1answer
62 views

Are there any “complete” languages in $coNP -NP$?

Suppose $coNP \neq NP$ language B would be called "complete" in $coNP-NP$ if: $B\in coNP - NP$ $A\in coNP-NP \implies A\leq_pB$ Are there any "complete" languages in $coNP - NP$?
2
votes
1answer
45 views

D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$

Given that a language D has a polynomial verifier, and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space. How can I prove that $D\in P$ ? My idea was to ...

1
2 3 4 5
10