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
31 views

Can you help me provide some examples of 3-co-SAT?

Recently I'm studying 3SAT problem, which is a NP-complete problem. I feel that it's easy to find a boolean formula which is satisfiable,but how about boolean formulas which are unsatisfiable, namely ...
1
vote
1answer
173 views

NP-completeness of satisfiability of formula over 50 variables

Given a boolean formula $F$ of length $n$ defined over a fixed number of variables (say 50), is it NP-complete to decide whether $F$ is satisfiable?
0
votes
0answers
15 views

Complexity class of computation of Homfly polynomial

It is claimed that "the problem of the computation of the homfly polynomial is NP-hard." but is it known if it is NP-complete? By the definition of NP-completeness, wouldn't it be enough to ...
1
vote
1answer
33 views

Reduction from SAT to SAT with exactly k true variables

Let $L$ be defined as follows: $\small L = \{(\phi, k) \mid \phi \in SAT \mbox{ and there is a satisfying assignment for $\phi$ having exactly $k$ true variables} \}$ I am struggling to show that $SAT\...
0
votes
1answer
29 views

If $A\leq_P B$ and $B\in \text{NP}$, is $A\in \text{NP}$?

Let $A\leq_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq_P B$ and $B\in \text{P}$ then $A\in \text{P}$. My question is, if $A\leq_P B$ and $B\in \...
-1
votes
1answer
28 views

K-Path-Problem is in $P$ or $NPC$

Given an undirected graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of at least length $k$ exists between these two vertices? How can we solve this problem? I think ...
2
votes
3answers
565 views

Are there problems in NP that do not reduce in polynomial time to any problem in NP?

As the title says: are there problems in $\mathbf{NP}$ that do not reduce in polynomial time to any problem in $\mathbf{NP}$?
1
vote
1answer
19 views

Consequences of a polytime algorithm for a decision problem reducible to 3SAT

If there is a polynomial time algorithm for a decision problem $A$, which is m-reducible to 3SAT, and 3SAT is NP-complete, does this prove that P=NP?
1
vote
0answers
30 views

Approximation classes for optimization problems with real values

Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.? If my understanding is correct a ...
1
vote
1answer
36 views

How to convert Bipartite Perfect Matching to SAT?

SAT is $NP$-complete while Bipartite Perfect Matching is in NC under derandomization assumptions. How to convert Bipartite Perfect Matching from balanced bipartites to SAT without Cook-Levin?
0
votes
1answer
25 views

If problem A reduces to an NP-Complete problem B, can we say that A is in NP?

I was reviewing All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete? I understand that the general way we show a problem A is in NP is to show there exists a poly-...
3
votes
1answer
81 views

Is 3-UNSAT problem coNP-complete?

The 3-SAT problem, i.e. the problem whether a given Boolean formula consisting of clauses of at most 3 literals is known to be NP-complete. Then it’s complement, i.e. whether such a formula is ...
0
votes
1answer
52 views

Tic-Tac-Toe in PSPACE

Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
-5
votes
1answer
63 views

Really confused

Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this? P = NP P ⊊ NP P ≠ NP NP ⊆ P
0
votes
1answer
34 views

How to prove that the generalized assignment problem (GAP) is NP-hard?

Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness? The decision version of the generalized assignment problem is to determine ...
1
vote
1answer
57 views

What does an NP reduction look like?

From my theory of computation lecture I recall: If $A \le_m B$ and $B$ is decidable then $A$ is decidable (uses a computable function as a reduction). If $A \le_p B$ and $B$ is in P then $A$ is in P ...
3
votes
0answers
37 views

Reduction from Edge-Coloring and Vertex-Coloring to a new problem

I have a question from a test I did and failed, a question I failed to do. In short: the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined. The new ...
0
votes
1answer
61 views

Reduction from problem A to another problem B

I have a question from a test that I failed to pass, I failed to do the question. The question: Let A and B have two languages so that there is a reduction function f: $A\leq _pB$. Suppose that $A \in ...
1
vote
2answers
56 views

Reduction between CLIQUE to SUBSET SUM

I have a question from a test that I failed to pass, I failed to do the question. The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
2
votes
1answer
37 views

Reduction from language in P to another language in NP

I have a question I was unable to do, from a last test I had. This is the question: Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
5
votes
1answer
91 views

Reduction from the SAT problem to the NAE-SAT problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
0
votes
1answer
23 views

Reduction from the Clique problem to the Odd Clique problem

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question: Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
0
votes
1answer
32 views

Complications of a language that reaches a state of reject

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question Let's look at the language $L_\mathrm{reject} = ${ $\left \langle M,w \right \...
-2
votes
1answer
45 views

Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u} [duplicate]

How can I reduce Subsetsum (or maybe other np-complete problem) problem to the problem below? input : a weighted graph $G$ and numbers $l$ and $u$. output : Does $G$ has spanning tree, $S$, such that $...
4
votes
2answers
126 views

tautology vs satisfiability

I had a test that I failed to pass, and it had a question that I failed to do. This is the question: Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on ...
2
votes
1answer
68 views

Reduction from TSP to even TSP

I have a question from a test that I failed to pass, I failed to do the question. The question: Let's look at the problem of the even-length traveling agent. Given graph $G = (V,E)$ and a weight ...
2
votes
1answer
69 views

Complexity of the language that enters an infinite loop

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. This is the question Let's look at the language $L_\mathrm{loop} = ${ $\left \langle M,w \right \rangle$ | ...
3
votes
2answers
216 views

Relationship between complexity classes W[1] and NP?

I am trying to understand the connection between The W-hierarchy as presented in chapter 13 of this book by Cygan et al. and the notion of the NP problems. Is the existence of an FPT algorithm for a ...
1
vote
3answers
51 views

Relationship between NP and CoNP

I have a question from a test that I could not pass, I could not answer the question and I am looking for help with this question This is the question Will be $A\in NP$ Suppose that $A\notin CoNP$. ...
3
votes
2answers
53 views

Reduction with CoNP and CoNPC

I have a question I was unable to do, from a last test I had. This is the question: Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$. Determine ...
0
votes
1answer
27 views

How to know if language is in comp or np?

I'm new to the site. I had a test a few days ago and failed it, I had a question I did not understand. This is the question: Let's look at the FALSE language: Collect all the verses P in the form of ...
1
vote
1answer
24 views

Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, prove $L(M)=CLIQUE$

Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, when the sum of a clique is the sum of the weights on all of the edges. I ...
1
vote
1answer
37 views

Why this problem is NP-Hard?

I'm asking about the question described here: Knapsack Problem with exact required item number constraint Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check ...
0
votes
1answer
46 views

How to prove Dense Subgraph problem is in NP

I have been studying NP-Complete problems and I saw the Dense Subgraph problem. Then I saw that they are trying to show that the problem is NP (see below quote), but I can't understand how it verifies ...
1
vote
1answer
21 views

NP problem: certificate concept clarification

When proving a problem in NP, e.g. k-clique problem defined as k-clique:= {<G,k>| G has a clique of size at least k }, from what I understand is that all we assume for the certificate "c&...
2
votes
0answers
30 views

How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?

Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get? So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...
3
votes
0answers
39 views

NP-complete problem

Is the following line true? Consider three problems A, B and C. If $A$ $<p$ $B$ and $B$ $<p$ $C$ and $B$ is NP-complete problem, then $C$ is also NP-complete. If B is NP-complete, then C would ...
0
votes
1answer
38 views

NP Reduction - Dominating set to SAT

Given a graph G and an integer k , recognize whether G contains dominating set X with no more than k vertices. And that is by finding a propositional formula ϕG,k that is only satisfiable if and only ...
1
vote
1answer
46 views

Does $NP^{SAT}=NP^{NP}$?

Does $NP^{SAT}=NP^{NP}$? We can see easily that $NP^{SAT}\subseteq NP^{NP}$, because $SAT \in NP$. But is the other side $NP^{NP}\subseteq NP^{SAT}$ also true? If yes, how can we prove it?
2
votes
3answers
110 views

Easy proof for $Primes \in NP$

I want to show that $Primes \in NP$ an I've seen multiple proofs that use facts from number theory, like this one. But isn't it much easier to proof $$Composites=\{x\in \mathbb{N}\cup\{0\}:x=1 \vee\...
1
vote
1answer
26 views

If $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?

Is it true that if $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$? I couldn't find any answer to that question. My attempt at proving it: If $S\in\left(NP\bigcup coNP\right)$, ...
1
vote
1answer
40 views

polynomial reduction within Np

If $A \le_p B$ and $B\in NP$, does it necessarily follow that $A\in NP$? ($\le_p$ is a polynomial many-one reduction) A quick yes/no comment is enough, a proof would be nice :-)
2
votes
1answer
27 views

Language in $R \setminus \mathit{NP}$

I am wondering whether the language $$L_{\textrm{hanoi}} = \{\langle k,s \rangle \mid \text{$s$ is a solution of Tower of Hanoi problem on $k$ rings}\}$$ is in $R\setminus \mathit{NP}$. I want to ...
0
votes
1answer
71 views

Assume P != NP, are these assertions valid?

Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$. Are the following assertions valid? $A \le_{P} B$ $B \le_{P} A$ My approach: $B \le_{P} A$ isn't valid, ...
-1
votes
1answer
42 views

Are the following assertions true if P != NP?

We consider the NP-complete $CLIQUE$ problem. Let furthermore $MST^*$ be the minimum spanning tree problem. Assume that $P \ne NP$ and explain whether the following assertions hold: $MST^* \le_{P} ...
2
votes
1answer
44 views

Is quadratic nonresiduosity in $\textbf{NP}$?

The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an ...
0
votes
2answers
96 views

How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem

Task: A Hamiltonian path of a graph is a path that visits all nodes of the graph exactly once. The hamiltion path problem (HPP) consists in deciding whether a given graph has such a path. Similarly, ...
0
votes
2answers
42 views

Is every problem with an output's size that grows polynomialy np?

I am wondering if every problem with an output's size that grows polynomialy is $\textsf{NP}$? My thinking is every $\textsf{NP}$ problems can be solved in polynomial time by a non-deterministic ...
1
vote
1answer
31 views

Non-brute force algorithm for a Eulerian like path

I have a graph with an arbitrary amount of edges and vertexes. Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one ...
0
votes
1answer
37 views

Karp's reduction strategy

One way to prove that a problem $X$ is NP-Complete is to pick two NP-Complete problems $Z$ and $W$ and show that ($\leq_p$ is polynomial reduction): $$\begin{array}{rr}X \leq_p Z & (1)\\W \leq_p X&...

1
2 3 4 5
13