8
votes
2answers
166 views

Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete

I encounter this problem recently and I want to know whether it is NP-Complete or solvable in polynomial time: Given a undirected weighted bipartite graph $G = (V, E)$ where $V$ can be partitioned ...
6
votes
4answers
347 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
1answer
80 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
1answer
136 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?
2
votes
0answers
116 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 ...
20
votes
1answer
775 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 ...
2
votes
0answers
126 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 ...
1
vote
0answers
71 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 ...
5
votes
0answers
107 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
6answers
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 ...
6
votes
1answer
606 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 ...
0
votes
0answers
280 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
1answer
504 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
2answers
527 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 ...
7
votes
2answers
979 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
1answer
815 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) ...
0
votes
1answer
505 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
0answers
230 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
0answers
211 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
votes
0answers
183 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 $$ ...
9
votes
4answers
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
0answers
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
2answers
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
2answers
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
3answers
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
1answer
310 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
1answer
489 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
3answers
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
1answer
788 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
3answers
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
5answers
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
2answers
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
4answers
2k 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 ...
6
votes
4answers
2k views

Characterize P^NP

What can you say about the complexity class P^NP, i.e. decision problems solvable by a polytime TM with an oracle for SAT? Obviously P^NP is in PH somewhere between NP union coNP, and Sigma2 ...
0
votes
3answers
419 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?