# Tag Info

### 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/...
• 1,516

### 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 ...
• 8,273
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 ...
• 1,714