Questions tagged [np]
In computational complexity, NP is the complexity class consisting of problems whose yes instances can be verified in polynomial time. NP stands for 'nondeterministic polynomial time '.
135 questions
8
votes
1
answer
403
views
one-dimensional (sort of) tilings
Consider the following one-dimensional tiling problem. Each "tile" is a sequence of nonnegative integers. A "region" is also such a sequence. I can shift the "tiles", or reverse them. A tiling is ...
- 423
2
votes
2
answers
553
views
Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph
I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.
One of the respondents cited Professor David Speyer's Math ...
- 21
6
votes
0
answers
1k
views
Is Logical Min-Cut Problem, NP-Complete? [closed]
Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by ...
- 161
3
votes
1
answer
1k
views
#P version of SUBSET SUM
The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
- 149
6
votes
1
answer
1k
views
NP-hardness of a graph partition problem?
I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is ...
- 2,993
6
votes
0
answers
472
views
Any approximation algorithms for self-avoiding walks?
I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
- 565
1
vote
0
answers
357
views
Is this minimization problem NP-Complete ?
We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.
...
- 209
1
vote
1
answer
1k
views
Knapsack Problem Specifics [closed]
(i) Are there limits on how many numbers must be in the set? { 1, 2 } or { 1, 5, 7, 8 , 9}
(ii) Are there limitations on how diverse or similar the numbers in the set can be? Coprime? Pairwise? { 1, ...
- 13
2
votes
2
answers
687
views
Could this be a NP complete?
Given a undirected and unweighted graph G(V,E). M is a subset of vertices of V.
s is a vertex in V - M.
Find an optimal tree T of G defined as:
(1) M and s are in V(T)
(2) Distance (which is ...
- 131
2
votes
2
answers
206
views
how to find vertex of parallelotope closest to given point P in R^n ? (Or minimize quadratic form over {+-1}) Is it NP ?
Consider a parallelotope in R^n and some point "P" in R^n.
What algorithms (except of brute force) can be suggested to find the closest vertex of paralleloptope to "P" ?
Is it NP ?
Parallelotope ...
- 24.9k
6
votes
1
answer
2k
views
Closest vector problem (=nearest lattice point) is trivial for "reduced lattice" ?
Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). The problem is to find "nearest" lattice point. The problem is known NP-hard in general it ...
- 24.9k
8
votes
2
answers
3k
views
How to find nearest lattice point to given point in R^n ? Is it NP ?
Consider some lattice in R^n.
Take some point "P" in R^n (which does not belong to this lattice in general).
What are the algorithms to find some nearest lattice point to "P" ?
"Nearest" - means in ...
- 24.9k
44
votes
4
answers
5k
views
Why is "P vs. NP" necessarily relevant?
I want to start out by giving two examples:
Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a planar $...
- 25.5k
7
votes
1
answer
2k
views
Is pattern recognition NP-complete?
Hello,
is the problem of pattern recognition (for a given sequence of n numbers, find the shortest Turing machine with an alphabet of 42 elements that will output these n numbers in, say, 5*n^3 time) ...
- 233
4
votes
4
answers
744
views
How to find the $\pm 1$ vector that is closest to a given vector $(r_1, \dots, r_l)$? Is it in NP? What algorithms are available?
Given a real vector $R = (r_1, \dots, r_l)$ and a set of $n$ distinct vectors
$$\begin{array}{c}
V_1 = (c_{1,1}, \dots, c_{1,l})\\
V_2 = (c_{2,1}, \dots, c_{2,l})\\
\vdots\\\
V_n=(c_{n,1}, \dots, c_{...
- 24.9k
0
votes
1
answer
755
views
A few questions about Computational Problems Complexity Classification
(This might look like just a post to you and you might think I shouldn't have submitted it as a question here but in reality it is some questions put together, so I hope you don't close it)
I only ...
- 103
2
votes
0
answers
313
views
Complexity of a variant of the Mandelbrot set decision problem?
This is a modified version of a question posted on StackExchange TCS.
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define
$M=${$(c,k,r)...
- 2,993
1
vote
0
answers
259
views
Self-improvement property of optimazation problems?
Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ...
- 2,993
4
votes
1
answer
248
views
Constructing hard inputs for the complement of bounded halting
If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
\text{coBHP}=\{\...
22
votes
5
answers
5k
views
Why relativization can't solve NP !=P?
If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only.
When I learnt to the topic of relativization ...
- 581
2
votes
0
answers
2k
views
Quantum computation implications of (P vs NP) [duplicate]
Possible Duplicate:
What impact would P!=NP have on the characterization of BQP?
Before I begin, I had a similar post closed for mentioning the recently released (to be verified) proof that P!=...
- 267
12
votes
2
answers
3k
views
What impact would P!=NP have on the characterization of BQP?
Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...
- 267
31
votes
3
answers
3k
views
Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?
Question. Given a Turing-machine program $e$, which
is guaranteed to run in polynomial time, can we computably
find such a polynomial?
In other words, is there a
computable function $e\mapsto p_e$, ...
- 236k
9
votes
3
answers
1k
views
Non-existence of algorithm converting NP algorithm to P algorithm?
[Edit: in the light of Nate Eldredge's answer below I rephrase the question]
P=NP is equivalent to the existence of a map of the following form:
Input: a polynomial-time non-deterministic Turing ...
- 2,885
2
votes
1
answer
353
views
poly-time algorithm to choose elements of sets
Let $A_1,A_2,\ldots,A_k$ be finite sets. Furthermore, for each $i\in\{1,2,\ldots,k\}$, let $B_i$ be a set whose elements are subsets of $A_i$.
Is there any polynomial-time algorithm that decides ...
- 85
5
votes
1
answer
540
views
Minimal Backtracking Proof Tree
When trying to prove that a particular instance of a problem like graph coloring or SAT is unsatisfiable, generally one explores the search tree using an algorithm like DPLL and the proof of ...
- 601
11
votes
3
answers
4k
views
Is this a well known NP-complete problem?
I came across this problem recently and I wanted to know whether it was a well known NP-complete problem. I checked the library but could not find anything that matched exactly.
Given a directed ...
- 111
5
votes
1
answer
2k
views
BPP being equal to #P under Oracle
Luca Trevisan here gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle.
In a similar vein, I was wondering if there were any results on $BPP^{NP}\stackrel{?}{...
- 601
22
votes
3
answers
6k
views
Satisfiability of general Boolean formulas with at most two occurrences per variable
(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...
- 4,729
18
votes
5
answers
8k
views
What techniques exist to show that a problem is not NP-complete?
The standard way to show that a problem is NP-complete is to show that another problem known to be NP-complete reduces to it. That much is clear. Given a problem in NP, what's known about how to ...
- 118k
14
votes
2
answers
4k
views
Best-case Running-time to solve an NP-Complete problem
What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...
- 597
24
votes
4
answers
5k
views
Super-linear time complexity lower bounds for any natural problem in NP?
Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd ...
- 2,416
12
votes
5
answers
5k
views
Characterize P^NP (a.k.a. Delta_2^p)
What can you say about the complexity class $\text{P}^{\text{NP}}$, i.e. decision problems solvable by a polytime TM with an oracle for SAT? This class is also known as $\Delta_2^p$.
Obviously $\text{...
- 213
1
vote
3
answers
1k
views
How can one characterize NP^SAT?
Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?
- 213