Most Popular
1500 questions
16
votes
1 answer
Can we approximate the number of words accepted by an NFA?
Let $M$ be an acyclic NFA.
Since $M$ is acyclic, $L(M)$ is finite.
In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete.
The second answer for that question provides a counting…
R B
- 9,448
- 5
- 34
- 74
16
votes
1 answer
To what extent can the mathematics of Reals be applied to Computable Reals?
Is there a general theorem that would state, with proper sanitization,
that most known results regarding the use of real numbers can actually
be used when considering only computable reals? Or is there a proper
characterisation of results that…
babou
- 1,542
- 10
- 18
16
votes
3 answers
Is there an online-algorithm to keep track of components in a changing undirected graph?
Problem
I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected components of this graph.
Properties
Additional…
bitmask
- 361
- 2
- 11
16
votes
0 answers
Is graph coloring complete for poly-APX?
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for all vertices of the given graph.
The complexity…
Hermann Gruber
- 6,470
- 1
- 35
- 58
16
votes
1 answer
Reference for (odd-hole,antihole)-free graphs?
X-free graphs are those that contain no graph from X as an induced subgraph. A hole is a cycle with at least 4 vertices. An odd-hole is a hole with an odd number of vertices. An antihole is the complement of a hole.
The…
András Salamon
- 19,000
- 3
- 64
- 150
16
votes
1 answer
Extensions of beta-theory of lambda calculus
The beta-eta-theory of the lambda-calculus is Post-complete. Can additional rules be added to extend the beta-theory of the lambda-calculus to get confluent theories other than the beta-eta theory?
Postscript
This question violated my own rule that…
Charles Stewart
- 4,316
- 28
- 45
16
votes
3 answers
Is the 3-sphere recognition problem NP-complete?
It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere
is in NP, via work by
Saul Schleimer in 2004: "Sphere recognition lies in NP"
arXiv:math/0407047v1 [math.GT].
I am wondering if this has been established to be…
Joseph O'Rourke
- 3,753
- 23
- 41
16
votes
3 answers
Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?
It is $NP$-hard to find a constant factor approximation of longest cycle in cubic Hamiltonian graphs. Cubic Hamiltonian graphs have at least two Hamiltonian cycles.
What are the best known upper bound and lower bound on the number of Hamiltonian…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
16
votes
1 answer
Can constant ambiguity reduce the state complexity of a regular languages?
We say that NFA $M$ is Constantly Ambiguous if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths.
If automaton $M$ is constantly ambiguous for $k=1$, then $M$ is called Unambiguous FA…
R B
- 9,448
- 5
- 34
- 74
16
votes
1 answer
Separation between coarse correlated equilibria and correlated equilibria
I am looking for examples of techniques for proving price of anarchy bounds that have the power to separate the price of anarchy over coarse correlated equilibria (the limiting set of no-external-regret dynamics) from the price of anarchy over…
Aaron Roth
- 9,870
- 1
- 43
- 68
16
votes
1 answer
Does Nisan's pseudo-random generator relativize?
Nisan proved in "Psuedorandom Generators for Space-Bounded Computation",
that there exists a pseudo-random generator which "fools" space-bounded computations.
Does this construction hold for every oracle (at least for non-adaptive queries) ?
Sebastian Ben Daniel
- 827
- 5
- 9
16
votes
2 answers
On the status of learnability inside $\mathsf{TC}^0$
I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\mathsf{TC}^0$, since I'm not an expert in the area.…
Suresh Venkat
- 32,071
- 4
- 95
- 271
16
votes
1 answer
How powerful is exact "quantum" computing if you suspend unitarity?
Short Question.
What is the computational power of "quantum" circuits, if we allow non-unitary (but still invertible) gates, and require the output to give the correct answer with certainty?
This question is in a sense about what happens to the…
Niel de Beaudrap
- 8,821
- 31
- 70
16
votes
1 answer
Can we distinguish strictly syntactic and semantic methods in programming language?
While discussion strong normalization proofs, this comment contrasts the "normal forms model" with "purely syntactic methods".
This brings me back to a more basic question: can we still distinguish syntactic and semantic constructions strictly, in…
Blaisorblade
- 2,059
- 21
- 29
16
votes
3 answers
UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?
Background:
In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary alphabet admits an assignment satisfying 1-$\epsilon$…
Daniel Apon
- 6,001
- 1
- 37
- 53