Strong co-nondeterministic lower bounds for NP cannot be proved feasibly.

Ján Pich Rahul Santhanam

Published in: STOC (2021)

Keyphrases

lower bound
np hard
upper bound
branch and bound
worst case
finite state
objective function
computational complexity
optimal cost
lower and upper bounds
upper and lower bounds
np complete
branch and bound algorithm
linear programming relaxation
linear programming
neural network
special case
machine learning