My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity. The wikipedia article on constructive proof begins, "a constructive ...
It is known, there exists oracles A, B s.t.: $P^A = NP^A; P^B \neq NP^B$, showing that any proof of P vs NP must be non-relativizing. Questions: (1) Can we actually use Oracles to separate ...
The Robertson-Seymour theorem on graph minors leads to some interesting conundrums. The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...