Timeline for Algebra in complexity theory
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2023 at 21:37 | history | edited | aeet | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Aug 28, 2023 at 21:06 | history | edited | aeet | CC BY-SA 4.0 |
added 25 characters in body
|
| Aug 28, 2023 at 20:06 | answer | added | D.W. | timeline score: 2 | |
| Aug 28, 2023 at 18:54 | comment | added | Joshua Grochow | Abstract algebra is regularly used in many parts of TCS (e.g. cstheory.stackexchange.com/q/16621/129 and cstheory.stackexchange.com/q/25841/129). Conjunctions of Boolean formulas are in general much more complicated than linear equations, as solving a system of Boolean formulas is NP-complete while (as you note) linear equations can be solved in polynomial time. | |
| S Aug 28, 2023 at 18:05 | review | First questions | |||
| Aug 28, 2023 at 23:35 | |||||
| S Aug 28, 2023 at 18:05 | history | asked | aeet | CC BY-SA 4.0 |