We suspect following relation: $$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit complexity model.

What are analogous complexity classes in BSS model and Valiant's arithmetic complexity model?

What are known relations and implications among complexity classes in these models?

What surprise would counter intuitive results such as $P=NP$ have on these hierachies and vice versa?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.