Tyson Williams
  • Member for 10 years, 11 months
  • Last seen more than a month ago
variations of SAT
17 votes

(Making comment an answer as requested and expanding a bit.) "A curious mind" should read Schaefer's dichotomy theorem and the generalization by Allender et al. that shows that every possible SAT ...

View answer
Real world applications of quantum computing (except for security)
17 votes

Efficiently simulating quantum mechanics.

View answer
Complexity of Portal 2
14 votes

(An earlier version of this question asked if anyone has shown Portal 2 to be NP-hard.) Yes, someone has done this. Portal 2 is at least NP-hard. My friend created a proof-of-concept map showing ...

View answer
CLRS's Fibonacci Heap size(x) analysis has a flaw?
Accepted answer
12 votes

In CLRS, $s_k$ is defined to be "the minimum possible size of any node of degree $k$ in any Fibonacci heap." Assuming your example data structure is a valid Fibonacci heap, your Fibonacci heap has a ...

View answer
Complexity of counting the number of edge covers of a graph
11 votes

I don't know where this was first proved, but since EdgeCover has an expression as a Boolean domain Holant problem, it is included in many Holant dichotomy theorems. EdgeCover is included in the ...

View answer
What hierarchies and/or hierarchy theorems do you know?
11 votes

Dieter van Melkebeek and coauthors have time and space hierarchies for semantic models with advice, including randomization. Dieter van Melkebeek, Konstantin Pervyshev: A Generic Time Hierarchy with ...

View answer
Surprising algorithms for counting problems
11 votes

In the Holant framework, there are several cases that are tractable (for non-trivial) reasons other than via matchgates in planar graphs. 1) Fibonacci Gates 2) Any set of affine signatures. 3) Non-...

View answer
Golden ratio or Pi in the running time
10 votes

Another example of $\varphi$ in the base is an algorithm by Andreas Björklund and Thore Husfeldt to compute the parity of the number of directed Hamiltonian cycles, which runs in time $O(\varphi^n)$. ...

View answer
Gröbner bases in TCS?
10 votes

I used a Gröbner basis to help find a short proof of a new dichotomy theorem for #CSP problems over 3-regular graphs with a single binary constraint function that has complex weights (arXiv version). ...

View answer
Why does most cryptography depend on large prime number pairs, as opposed to other problems?
9 votes

Boaz Barak addressed this in a blog post My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of ...

View answer
What are infinite graphs good for?
9 votes

In the anti-ferromagnetic region of the Ising model, the computation complexity of approximating counting depends on the Gibbs measure over infinite $d$-regular trees. The Gibbs measure on these ...

View answer
Number of subgraphs with a given number of nodes
Accepted answer
9 votes

Let $f(G, k_1, k_2)$ be the counting problem that you have defined. Then $$g(G) = \sum_{k_1 = 0}^{|V_G| / 2} f(G, k_1, 2 k_1)$$ counts the number of matchings in $G$, which only uses a linear number ...

View answer
Survey on #P and/or counting problems
9 votes

Pinyan Lu published a survey via ECCC in mid 2011. It compares three popular counting frameworks: Counting Graph Homomorphisms, Counting Constraint Satisfaction (#CSP), and the Holant framework (and ...

View answer
Are there non-constructive algorithm existence proofs?
8 votes

Yes. At one point in (1), the complex-weighted counting graph homomorphism dichotomy theorem for any finite domain size, Cai, Chen, and Lu only prove the existence of a polynomial-time reduction ...

View answer
The ODD EVEN DELTA problem
7 votes

UPDATE: I should have pointed out that the answer below is about the special case of $k = |V|$. Since this case is hard, the problem for general $k$ is also hard. The Holant framework is ...

View answer
Number of subgraphs with given edge parity
Accepted answer
7 votes

This problem is tractable. Let $G = (V,E)$ be the input graph with $|V| = n$ and let $e$ and $o$ be the number of vertex-induced subgraphs of $G$ with an even and odd number of edges respectively. Of ...

View answer
Is there a backup/replacement for the Complexity Zoo?
7 votes

Scott Aaronson just reported that the Complexity Zoo is down because the graduate student that was hosting it has graduated. To get the Complexity Zoo working again, we need someone to host and a ...

View answer
Uses of quasi-PERs/difunctional relations/zig-zag relations?
6 votes

I don't know about the field of semantics, but the concept you mention is crucial in the complexity of counting. I have not seen a relation $R$ called a difunctional relation before, but it is ...

View answer
counting independent sets
6 votes

To supplement the answer from @RJK, as of yesterday, there is a new "state of the art." Sly and Sun show Theorem 1. For $d \ge 3$ and $\lambda > \lambda_c(d) = \frac{(d−1)^{d-1}}{(d-2)^d}$, ...

View answer
The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems
6 votes

The prover is "all-powerful and possesses unlimited computational resources" so it has no need of random bits. Thus the only randomness is the randomness of the verifier. If the prover uses random ...

View answer
Problems with no known quantum advantage
5 votes

This is not in NP, but comparison-based sorting. The $\Omega(n \log n)$ lower bound is information theoretic.

View answer
Why do theoreticians in CS use multiple-letter variables?
Accepted answer
5 votes

I agree with the arguments for shorter variable names on the math.se question, but I disagree that "the pros of shorter names seem to apply more to TCS than those of longer names". In particular, I ...

View answer
Deciding graph homomorphism
5 votes

Deciding if there is a graph homomorphism is easier than counting the number of (weighted) graph homomorphisms. Weighted Case For undirected target graphs $H$ (i.e. the number of weighted graph ...

View answer
The origin of the terms "efficient" and "feasible" computation/algorithm
5 votes

Another phrase to consider is "exactly solvable", which is from statistical physics and also corresponds with our present-day notions of efficient/feasible. The introduction in this paper contains a ...

View answer
Intermediate Problems between FP and #P
4 votes

Use Schöning's theorem: Let $A_1$, $A_2$ be recursive sets and $C_1$, $C_2$ be classes of recursive sets with the following properties: $A_1 \notin C_1$, $A_2 \notin C_2$ $C_1$ and $C_2$ ...

View answer
Number of edge induced subgraphs with given vertex parity
4 votes

For simplicity, let's restrict ourselves to $k$-regular graphs. The first part of your update is correct. Changing notation slightly from what you have introduced, let me define $n_e$ (resp. $n_o$) ...

View answer
Counting number of solutions to a specific SAT formula
4 votes

This is not an answer, just a long comment. First, you say that you are unsure if this problem in in #P. It depends on how you define your input, which can either be the $n$-by-$n$ graph or just $n$....

View answer
Examples of #P problems which are in FP ?
4 votes

Yes. Boolean Domain For Boolean variables, the set of product type functions $\mathcal{P}$ contains functions that are products of (1) binary equality, (2) binary disequality, (3) and unary functions. ...

View answer
Finding a ranking which minimizes the number of conflicts
4 votes

Your conflict measure is called the Kendall tau distance. The total order that minimizes these conflicts is the winner of the Kemeny-Young voting method. Computing the winner of the Kemney-Young ...

View answer
Is there an efficient algorithm to determine the parity of the longest path in a graph?
4 votes

Based on Gadi's answer on Math.SE (which proves NP-hardness using a Cook reduction), here is a proof of NP-hardness using a Karp reduction (as requested). General case The reduction is from ...

View answer