Reputation
20,223
Next privilege 25,000 Rep.
Access to site analytics
Badges
5 80 144
Newest
 Good Answer
Impact
~259k people reached

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