3 ms·
This finds a certificate for positive instances, but without a complexity bound can this be made to solve the decision problem in the presence of negative insta
by CaptainNegative 5y ago
This finds a certificate for positive instances, but without a complexity bound can this be made to solve the decision problem in the presence of negative instances?
- deleted 5y ago[deleted]
- lovecg 5y agoI had to look this up since it’s been a while, but looks like no - this is not a full solution. It correctly accepts the positive instances in polynomial time but no algorithm is known that would fully decide all instances in polynomial time.