Most Popular
1500 questions
18
votes
1 answer
Best known joint containments for/by NP and Parity-P?
Parity-P is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero number of acceptance paths). Thus Parity-P is…
Niel de Beaudrap
- 8,821
- 31
- 70
18
votes
2 answers
Polynomial time solvable instances of Max-Sat
The problem Max-Sat ask you to find an assignment of a CNF formula which satisfy as many clauses as possible.
For the simpler problem SAT there are many known special cases which can be solved in polynomial time, e.g. we can solve 2-SAT in…
Martin Vatshelle
- 1,339
- 7
- 21
18
votes
1 answer
Equivalence of feasibility checking and optimization for linear systems
One way to show that checking the feasibility of a linear system of inequalities is as hard as linear programming is via the reduction given by the ellipsoid method. An even easier way is to guess the optimal solution and introduce it as a…
Suresh Venkat
- 32,071
- 4
- 95
- 271
18
votes
1 answer
What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?
Following Josh Grochow's suggestion, I am converting my comment from a previous question into a new question.
What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?
Here $\mathsf{UP}$ is the class of languages recognizable by polynomial time…
Sasho Nikolov
- 18,189
- 2
- 67
- 115
18
votes
2 answers
Co-NP-completeness of minimal TSP tour?
This problem came out of my recent blog post, suppose you are given a TSP tour, is it co-NP-complete to determine if it is a minimal one?
More precisely is the following problem NP-complete:
Instance: Given a complete graph G with edges weighted…
Lance Fortnow
- 8,681
- 44
- 59
18
votes
2 answers
Bounds on the size of the smallest NFA for L_k-distinct
Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal:
$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne…
R B
- 9,448
- 5
- 34
- 74
18
votes
4 answers
Open problems related to Graph isomorphism
Presently I am doing literature survey on Graph isomorphism (GI) problem.
I would like to know some open questions related to the following
What are the graph parameters for which fixed parameter tractability of GI is an open problem.
What are…
Kumar
- 2,044
- 13
- 27
18
votes
3 answers
Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity
While searching The information System on Graph Classes and their Inclusions, I found several graph classes for which the Hamiltonian Cycle problem is NP-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
18
votes
3 answers
In what class are randomized algorithms that err with exactly 25% chance?
Suppose I consider the following variant of BPP, which let us call E(xact)BPP:
A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly 3/4 probability and every word not in the language…
domotorp
- 13,931
- 37
- 93
18
votes
2 answers
Full Completeness vs Full Abstraction of a program translation
Compiler verification efforts often come down to proving the compiler fully abstract: that it preserves and reflects (contextual) equivalences.
Instead of providing full abstraction proofs, some recent (categorical based) compiler verification work…
Phillip Mates
- 485
- 2
- 7
18
votes
2 answers
A Boolean function that is not constant on affine subspaces of large enough dimension
I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension of this subspace is $o(n)$.
It is not difficult…
Alexander S. Kulikov
- 895
- 5
- 11
18
votes
2 answers
Graph Isomorphism Problem
I am doing some literature review on Graph isomorphism problem. Most of papers which I am reading are written by E.M Luks and Laszlo Babai.
These papers uses the high level knowledge of group theory and complexity theory.
As I am new to this field…
Kumar
- 2,044
- 13
- 27
18
votes
2 answers
Maximum number of internally vertex-disjoint odd length s-t paths
Let $G$ be an undirected simple graph and let $s,t \in V(G)$ be distinct vertices. Let the length of a simple s-t path be the number of edges on the path. I am interested in computing the maximum size of a set of simple s-t paths such that each path…
Bart Jansen
- 5,265
- 21
- 39
18
votes
5 answers
Why economists should care about computational complexity
When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and chapter 11 of Scott Aaronson's essay. These posts are…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
18
votes
1 answer
Complexity of interval cover problem
Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to select a minimum number of intervals $[l_i,r_i]$…
Torsten Mütze
- 181
- 4