What Happens if P=NP?
Last edited: August 8, 2025…what can we solve efficiently?
the “easy” cases
by definition all NP/NP Complete problems…
- SAT
- 3COL
- Hamiltonian path problem
- and also anything in coNP because if \(\text{P}= \text{NP}\), then \(\text{NP} = \text{coNP}\)
- UNSAT
- NOT-3COL
- …
review: certificates definition of NP, coNP
\(L \in \text{NP}\) IFF \(\exists\) polytime verifier \(V\) such that \(x \in L \Leftrightarrow \exists w \in \qty {0,1}^{\text{poly}\qty(|x|)}, V\qty(x,w) = 1\)
\(L \in \text{coNP}\) IFF \(\exists\) polytime verifier \(V\) such that \(x \in L \Leftrightarrow \forall w \in \qty {0,1}^{\text{poly}\qty(|x|)} V\qty(x,w) = 1\)
When is AI Bad?
Last edited: August 8, 2025embodied settings, etc.
Who's Talking When?
Last edited: August 8, 2025Under Construction
whole metalanguage study
Last edited: August 8, 2025A study with the goal of identifying semantic primes.
Why is building a to-do list app so darn hard?
Last edited: August 8, 2025Why are Todo Lists (a.k.a. personal productivity systems) so hard to build well?
I’m genuinely curious. I was listening to the last episode of Cortex, and one of the hosts (CGP Grey) brought up a similar point regarding personal productivity platforms. OmniFocus, the reigning champion of the industry for professionals looking for a deeply customized system, has been staggering in their ability to ship the next version of their application. Much of the market consists of various different packagings of the same offering. Grey’s thesis of these platforms essentially boils down to this: