The np tag has no wiki summary.

**5**

votes

**4**answers

268 views

### NP-hard problems in linear algebra and real analysis [closed]

I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent.
I would thus like to collect in this thread a list of ...

**1**

vote

**1**answer

65 views

### Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language:
$L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$.
($G$ ...

**3**

votes

**1**answer

114 views

### Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?

**1**

vote

**1**answer

183 views

### Simple example of why Differential Equations can be NP Hard [closed]

Just looking for a simple example of why Differential Equations can be NP hard
Edit:
It appears that the answer below may be what I was looking for, but I am clarifying just in case:
Slides ...

**8**

votes

**3**answers

299 views

### Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation:
coloring in lattice
Reference for Wang Tile
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
...

**0**

votes

**1**answer

106 views

### How to determine the distance between two matrices under the meaning of a matrix function? [closed]

Suppose a nonlinear infinitely continous differentiable function $f:\mathbb{D}\mapsto \mathbb{R^+}$, where $\mathbb{D}\subset\left\{X|\text{rank}{X}=2,X\in\mathbb{R}^{3\times 3}\right\}$ is a ...

**2**

votes

**0**answers

92 views

### Partitioning a cubic graph into two induced cycles of equal order

I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord ...

**2**

votes

**3**answers

135 views

### Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...

**20**

votes

**1**answer

735 views

### How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...

**1**

vote

**0**answers

103 views

### Intermediate $\mathsf{NP}$-complete problems?

Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition problem is strongly ...

**8**

votes

**0**answers

203 views

### Testing contrasts in statistics: Is this provably a hard problem, or not?

Scheffé's method for identifying statistically significant contrasts is widely known. A contrast among the means $\mu_i$, $i=1,\ldots,r$ of $r$ populations is a linear combination $\sum_{i=1}^r c_i ...

**1**

vote

**3**answers

209 views

### Strategic vertex labeling

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...

**1**

vote

**0**answers

61 views

### Are set covering problems with nonlinear cost functions NP-Hard?

Are set covering problems (set cover problem wikipedia) with a nonlinear cost function also NP-hard? Is there a general result about this?
To be more specific the cost function I am interested in ...

**0**

votes

**2**answers

165 views

### Generating 3SAT circuit for Integer factorization example

I read somewhere that 3SAT can be used to solve Integer Factorization.
If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given ...

**1**

vote

**0**answers

118 views

### Non-trivial lower bound on the number of “Graph Diagonals”

The definition of Graph Diagonals, that are the subject of this question, is based on the notions of crossing edges and on connected graphs:
Two edges $AC$ and $BD$ of a complete, symmetric and ...

**4**

votes

**0**answers

102 views

### Are there sampNP-intermediate problems?

This questions is approximately cross-posted from theoretical computer science stackexchange
Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} ...

**12**

votes

**6**answers

1k views

### SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...

**0**

votes

**1**answer

84 views

### A simplified/harder 2-sequence longest common sub-sequence (LCS) problem

Basically, its a 2-sequence longest common sub-sequence (LCS) problem.
What's so special?
1: each alphabet only occurs 2 times, one in each sequence, which means with no same alphabet in one ...

**7**

votes

**1**answer

209 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 ...

**1**

vote

**1**answer

216 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 ...

**6**

votes

**0**answers

420 views

### Is Logical Min-Cut Problem, NP-Complete?

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 ...

**2**

votes

**1**answer

431 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 ...

**2**

votes

**0**answers

492 views

### 0,1 solution to system of linear integer equations.

I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...

**6**

votes

**1**answer

542 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 ...

**5**

votes

**0**answers

228 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 ...

**0**

votes

**0**answers

274 views

### Is this minimization problem NP-Complete ?

We are given an nx(n+k) matrix A, with entries in GF(2), of the form A=(In|B) where In is a nxn identity matrix where the matrix B has no "zero" rows or columns.
The problem is to partition the ...

**0**

votes

**1**answer

483 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, ...

**2**

votes

**2**answers

520 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 ...

**2**

votes

**2**answers

175 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 ...

**4**

votes

**1**answer

873 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 ...

**7**

votes

**2**answers

935 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 ...

**5**

votes

**1**answer

794 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) ...

**4**

votes

**4**answers

606 views

### how to find vector $(\pm 1, \pm 1, \pm 1, … \pm 1)$ which is most close to given vector (r_1,…r_l) ? Is it NP-problem ? What algorithms are available ?

Given:
some vector $R=(r_1...r_l)$ - real numbers,
and a set of distinct vectors with $+1$ or $-1$ coordinates
$$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\\
V_2=(c_{2,1} ... c_{2,l}),\\\
...

**0**

votes

**1**answer

486 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 ...

**2**

votes

**0**answers

225 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
...

**1**

vote

**0**answers

202 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 ...

**1**

vote

**0**answers

165 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 $M$ accepting
$$
\text{coBHP}=\{\langle ...

**9**

votes

**4**answers

2k 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 ...

**1**

vote

**0**answers

1k 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 ...

**11**

votes

**2**answers

2k 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 ...

**23**

votes

**2**answers

1k 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$, ...

**8**

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**

votes

**1**answer

304 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 ...

**5**

votes

**1**answer

482 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 ...

**6**

votes

**3**answers

2k 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 ...

**4**

votes

**1**answer

757 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 ...

**18**

votes

**3**answers

2k 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 ...

**13**

votes

**5**answers

3k 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 ...

**6**

votes

**2**answers

1k 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 ...

**13**

votes

**4**answers

1k 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 ...