Can Turing Machines Be Represented by Polynomial-Sized Circuits?

Join the discussion

Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.

Real named experts · corrections over time · the nuance an AI answer skips

1 reply · 2K views

Dragonfall

How do you show that every polynomial-time turing machine has a family of equivalent polynomial-sized circuits?

Physics news on Phys.org

.Scott

Similar threads