299 views

One of my favorites is $IND[t(n)] = FO[t(n)]$, where $IND[t(n)]$ is the class of problems decidable with an inductive definition which closes in less than or equal to $t(n)$ iterations and $FO[t(n)]$ ...

131 views

Lets say that we have $s, d$ where $log(s(n))^{d(n) - 1} = o(n)$. Let $d'(n)$ be arbitrary and $s'(n) = 2^{\sqrt[d'(n) - 1]{log(s(n))^{d(n) - 1}}}$. Then we have that $log(s(n))^{d(n) - 1} = log(s'(n))... View answer 3 answers 14 votes 1k views 4 votes To show satisfiability of$\exists x \forall y \phi$, we can play a game with two players A and B who each have access to a SAT solver. If we're working in a domain$D\$, then at each iteration (...

168 views

The answer given is adequate but I'd like to mention that once you reduce a term to normal form, without reflexivity you're out of luck, with reflexivity you've hit a fixed point and thus you can use ...

549 views

What you are asking for is methods in proving lower bounds on the computational complexity (measured in space, time, etc) of given computational problems, and the answer is mostly that we have made ...

2k views