2018
Jul
23
awarded  Nice Question
2017
Jun
28
awarded  Yearling
Apr
26
comment How can languages that are E-complete have sub-exponential size circuits?
Oh I see. That halting problem example is pretty neat.
Apr
26
accepted How can languages that are E-complete have sub-exponential size circuits?
Apr
26
awarded  Curious
Apr
25
asked How can languages that are E-complete have sub-exponential size circuits?
Apr
18
comment Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
@wchargin I think the mistake might be claiming that the TM runs in $2^{k \log \log n}$ time because you need to consider the head position of the input tape also while counting the number of configurations. So, I think the TM runs in time $n 2^{k \log \log n}$.
Apr
18
comment Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
@Choirbean It requires a proof using crossing sequences. You can look it up here cs.stackexchange.com/questions/7372/… .
Apr
17
comment Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
There's an interesting result related to this. Any Turing machine that runs in $o(\log \log n)$ space accepts a regular language.
Mar
3
comment Divide and Conquer majority element algorithm
If you're looking for a linear time algorithm, try this en.wikipedia.org/wiki/…
Mar
1
comment Do reductions form a total binary relation?
Let us continue this discussion in chat.
Mar
1
comment Do reductions form a total binary relation?
You said total, which I used to think meant computable. Like total Turing machines?
Mar
1
comment Do reductions form a total binary relation?
Oh ok. Also, you say that $\alpha$ and $\beta$ are computable functions. But aren't any two computable functions turing reducible to each other? The reduction Turing machine can simply compute the answer to the function without using the oracle.
Mar
1
comment Do reductions form a total binary relation?
What does extending a boolean function mean? Also, what does, "x not in the support of a_i" mean? Also, "if none of these runs ever terminates", how do we check this condition? If it never terminates, then we won't be able to construct the function. I don't know much about boolean functions so I don't understand most of the answer.
Mar
1
comment Do reductions form a total binary relation?
@D.W. Reductions can use an arbitrary amount of time (they need to halt on all inputs though). chi and AndreaAsperti have shown that this property is not true for $\leq_m$ reductions. Also, in the case of $\leq_T$ reductions, I think that both $A$ and $B$ need to be undecidable because if one of them is not, then it trivially reduces to the other. Also, if both languages are in the Arithmetical Hierarchy, then also one will reduce to the other (by definition). So, are there languages outside the hierarchy? (I am the asker, asked as a guest because I wasn't logged in).
Mar
1
revised Do reductions form a total binary relation?
Languages are subsets of sigma star
Mar
1
suggested approved edit on Do reductions form a total binary relation?
Feb
23
revised Finding optimal sequence of questions to minimize total student time
Added more relevant tags
Feb
22
comment Is 2QBF in P^NP?
2QBF is complete for the 2nd level of the polynomial hierarchy ($NP^{NP}$). So, if it is shown to be in ($P^{NP}$), wouldn't the polynomial hierarchy collapse (which is considered unlikely)?
Feb
21
revised Finding optimal sequence of questions to minimize total student time
Add decision version of the problem to help prove NP-hardness