Skip to main content
Theoretical Computer Science

Return to Question

Tweeted twitter.com/StackCSTheory/status/1189693483205955584
deleted 1 character in body
Source Link
VS.
VS.
  • 549
  • 3
  • 15

  1. What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?

  2. What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates can be solved in $2^{O(n-n^\alpha)}poly(nm)$$2^{(n-n^\alpha)}poly(nm)$ time?

  1. What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?

  2. What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates can be solved in $2^{O(n-n^\alpha)}poly(nm)$ time?

  1. What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?

  2. What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates can be solved in $2^{(n-n^\alpha)}poly(nm)$ time?

Post Undeleted by VS.
Post Deleted by VS.
Source Link
VS.
VS.
  • 549
  • 3
  • 15

What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?

  1. What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?

  2. What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates can be solved in $2^{O(n-n^\alpha)}poly(nm)$ time?