# Questions tagged [np]

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

553 questions
Filter by
Sorted by
Tagged with
36 views

### Implications in $\mathbb{NP}$-completeness

Suppose I have an $\mathbb{NP}$-Complete problem called problem $A$. Further, suppose that $A$ is poly-time solvable in undirected-acyclic graphs; in other words, trees. Now, If I take a problem ...
21 views

### Finding the common part of two systems of linear equations modulo 2

Given two systems of linear equations modulo 2, is there a method to find the common part (the equations which are true in both case) ? For example... Matrix 1: a⊕b=1 and c⊕d=0 and y=1 and e=0 Matrix ...
79 views

### Is NP in NP/Poly?

The answer is yes, NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function--the advice ...
15 views

### How can I create the table and solve the error, why did the error happened? [closed]

import world_population.csv population = Table.with_columns( "Population", population_amounts, "Year", years ) population No module named 'world_population'
59 views

### proving that a problem is in P

I read online that this problem is in P: Problem = {a^n, where n is a primary number} I can't find any algorithm that decides if a word w in ...
59 views

### Proving NP-completeness for a not so cheesy problem

Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. ...
42 views

### Why do I only need to reduce from one problem in NP to prove NP-Hardness?

Suppose I wish to show that my decision problem $Q$ is NP-Hard. Why do I need to reduce from one problem $Q'$ of known hardness ? Consider for instance the following situation: Here, I have my set NP ...
13 views

### Would $\mathsf{P=BPP}$ imply $\mathsf{dIP=IP}$ and if not then why?

Complexity class $\mathsf{IP}$ includes all problems that can be solved using an interactive proof system where the verifier is a probabilistic polynomial time machine, and the prover is a machine of ...
36 views

### If A is not in NP, and A reduces to B, does this mean B is not in NP?

I know it is true that if A is not in P, and A reduces B, then B is not in P. But is it true for NP as well? If A is not in NP, and A reduces to B, does this mean B is not in NP? Why or why not? ...
90 views

### How to Show Subset Sum $\le_p$ 3-Partition

Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete. Is it ...
15 views

### Showing that Subset Sum Reduces to 3-Partition [duplicate]

Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete. This is a ...
16 views

### For every $\mathrm{NP}$ language $L$, is there a verifier such that, for all the certificates $u$ of other verifiers of $L$, it accepts $(x, u)$?

Let $L$ be an $\mathrm{NP}$ language. Then there exists a verifier $V$ of $L$ and a polynomial $p\colon \mathbb{N} \to \mathbb{N}$, such that for every $x \in \Sigma^{*}$, $x \in L$ if and only if ...
37 views

### Proving the language of non-primes is in NP

I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question. Show the following language is in ...
36 views