# Tagged Questions

**9**

votes

**6**answers

1k views

### Non-constructive proofs vs. efficient algorithms

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 ...

**3**

votes

**1**answer

181 views

### Class Separation, Oracles, Relativization

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 ...

**19**

votes

**6**answers

2k views

### Can a problem be simultaneously polynomial time and undecidable?

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 ...