Tag Info

Accepted

smallest circuit size using XOR gates

This is NP-hard. See: Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7 The ...
• 26.4k
Accepted

Is the following graph optimization problem approximable within a constant factor?

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. ...
• 3,844

Are runtime bounds in P decidable? (answer: no)

On the positive side, it is decidable whether a one-tape Turing machine runs in time $n \mapsto C \cdot n + D$ for given $C, D \in \mathbb{N}$, see: David Gajser: Verifying whether One-Tape Non-...
• 26.6k
Accepted

Approximating #P-hard problems

We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$. Here are some ...
• 2,743
Accepted

Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

The answer for (1) is "unlikely". It is simple to show (reduce from $Partition$) there exists no $\alpha$-approximation for Bin Packing, for any $\alpha<\frac{3}{2}$, unless $P=NP$. That said, ...
• 9,378
Accepted

Does Max Planar 3-SAT admit a PTAS?

Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach. This has been observed, for instance, in Theorem 17 in Pierluigi Crescenzi and LucaTrevisan: "Max NP-...
• 5,712
Accepted

• 2,101

• 7,052

Is there any research on approximation of reals with computable numbers

It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and ...
• 4,400
Accepted

Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al

Section 1 of the paper, in which the first definition appears, is introductory. The formal development starts at Section 2. The part of the paper starting at Section 2 is completely self-contained. ...
• 14.1k

Are runtime bounds in P decidable? (answer: no)

The problem was also solved in my article "The intensional content of Rice's Theorem" POPL'2008, where I prove that no "complexity clique" is decidable. A complexity clique is a class of programs ...

Approximating #P-hard problems

Here is a reference to Bordewich, Freedman, Lovász, and Welsh that develops this topic to some extent.
• 5,386
Accepted

Minimum relevant variables in linear system - additive approximation

Unless $P=NP$, there does not exist a polynomial time approximation algorithm that returns solutions of value at most $\text{OPT}+d$. Suppose otherwise, and consider some fixed $d$ for which there ...
• 5,712
Accepted

Maximum Positive Negative Set Cover Problem

This problem has a few simple constant-factor approximation algorithms, such as the trivial algorithm that picks the $C' \in \{\emptyset, C\}$ with a higher objective score. Here's a loose constant-...
• 1,624
Accepted

Optimization problems with same optimal value, but different approximation behavior

What about something like minimum vertex cover vs. minimum fractional vertex cover (i.e., optimal solution of the LP relaxation of the vertex cover problem) in bipartite graphs? These two problems ...
• 11.3k

Where to find info on (polytime) approximability of various discrete optimization problems?

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/
• 5,424
Accepted

Best approximations of Minimum Dominating Sets in chordal graphs

The best approximation ratio that can be achieved in polynomial time should be $\Theta(\log n)$ where $n$ is the number of vertices. This can be seen by standard reductions from the Set Cover problem ...
Accepted

What is a "level-r pseudo expectation functional"?

The degree $r$ pseudo-expectation operator operates on polynomials of at most degree $r$. Since the pseudo-expectation operator is positive semidefinite, we're guaranteed that the square of a ...
• 2,295
If $\ell$ and $k$ are fixed, there are only finitely many possible problem instances, so you can write a program that has a hardcoded table of all possible instances and their solutions. Consequently,...