when eigenvalues of the problem setup is well-posed, eigenvalues should have a negative real part (because they are convergent); otherwise, if the eigenvalues have a positive real part, they are divergent and hence ill-posed

…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\)

embodied settings, etc.

Under Construction

A study with the goal of identifying semantic primes.