6 votes

Solving 3-SAT in O(n^6)?

You can find all weird stuff out there... For example, just google "graph isomorphism problem 2022", and the first search result is this polytime algorithm... https://www.biorxiv.org/content/...
user avatar
  • 1,516
6 votes

Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

Theorem 1. For all $n\ge 6$ and $T$ with $n+14\le T \le 7{n\choose 3}$, there is a satisfiable 3-SAT formula on $n$ variables with $T$ clauses in which all clauses are redundant. Before we give the ...
user avatar
  • 8,273
6 votes
Accepted

Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

I interpret the question as: given $n$ and $T$, what is the maximum number of redundant clauses a satisfiable $n$-variable formula on $T$ clauses can have? For the purposes of this question, I find it ...
user avatar
3 votes
Accepted

Upper bound on the expected number of correct bits via a "lossy compression"

Let $f(n,s)$ denote the answer. Claim: We have $f(n,s) = \frac{n}{2}+\Theta(\sqrt{sn})$ for any fixed $s$ as $n \to \infty$. More precisely, $\lim_{n \to \infty} \frac{f(n,s)-\frac{n}{2}}{\sqrt{n}} = \...
user avatar
2 votes

Is the center of a BFS tree a good approximation of the graphs center?

In the worst case, this algorithm gives a 2-approximation (the trivial upper bound). Take a cycle on some $n=4m$ vertices, vertex set $v_0,\ldots,v_{n-1}$, with one chord between $v_0$ and $v_{2m}$. ...
user avatar
  • 211

Only top scored, non community-wiki answers of a minimum length are eligible