Ryan Williams
Reputation
20,223
Next privilege 25,000 Rep.
 Nov 7 answered Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time? Nov 6 awarded Enlightened Nov 2 awarded Nice Answer Oct 23 comment Is there a non-deterministic linear time algorithm for CNF-SAT? @MichaelWehar if you use a counting sort, you can sort n keys in the range [0,k] in time O(n+k) in a reasonable random access model (e.g. Random access Turing machine, where you can take O(log n) time to write down an index, then can jump to that index of the tape in 1 step). If you encode each literal as an (log n+1) bit string, then the total number of clauses and variables is at most O(n/log n), in which case O(log n)-time operations on all the literals are fine. Extending to two tape TM is not straightforward, at least with counting sort. Oct 20 awarded Good Answer Oct 17 comment Proof that circuit upper bounds for $E$ imply $P \neq NP$ good point, Andras! One of the quantifiers in the $\Sigma_3 E$ part can be seen as solving MCSP. Oct 16 awarded Nice Answer Oct 16 answered Proof that circuit upper bounds for $E$ imply $P \neq NP$ Oct 14 awarded Nice Answer Oct 11 awarded Good Answer Oct 11 comment Nontrivial problems solvable in constant time? I think David Eppstein's suggestion points to a more interesting direction: considering randomized O(1)-time algorithms. At least in that case, you can hope that every input bit is accessed in at least one possible run of the algorithm. Oct 11 comment Nontrivial problems solvable in constant time? Don't think your example is $O(1)$ time. Your input has length $m=O(\log n)$, in which case the typical word RAM would only allow $O(\log m)$-bit operations in one step. (The alternative is to allow wordsize proportional to the input length, but in that case one can name many "constant-time" algorithms...) You could try to add on a string of length $\geq n$ after those numbers, but then I don't see how checking that format would run in $O(1)$ time: seems you have to check (via binary search, say) that the total string length is indeed $\Omega(\log n)$, which requires $\log n$ time. Oct 6 reviewed Close Log Rank Conjecture Collaborative Approach Oct 6 reviewed Close Partitions on Integer Permutations Oct 1 reviewed Close Is my language Turing-complete? Sep 26 awarded Custodian Sep 26 reviewed Close Practical example: how to formally verify “file name” implementation from a spec? Sep 26 reviewed Leave Open How Much Computing Power would be Required to Fully Simulate a Cubic Meter? Sep 26 reviewed Close Complexity of QBF with Restrictions on Models Sep 26 reviewed Close Computing the DAG of a program given source code or AST