1
$\begingroup$

I was solving problems related to P and NP where I encountered the following problem:
Given a standard definition of NP,
if x belongs to L then there exists y such that |y| <= |x|^d and A(x, y) = 1;
if x does not belong to L then for every y with |y| <= |x|^d we have A(x, y) = 0.

1. what is the new class formed when we don't include the second statement?
2. what is the new class formed when we don't include the first statement?
I am well versed with the definitions of P and NP but unable to figure out how to determine these new classes.
Any help in understanding these concepts would be appreciated.

$\endgroup$
1
$\begingroup$

Here is a big hint to help you solve the problem:

Can you give an example of a language that is in this class? Can you give an example of a language that is not in this class?

$\endgroup$
  • $\begingroup$ I am referring to standard 3SAT problem as a reference example to solve this problem. I am unable to figure out that how any input instance will not satisfy the circuits. I came to a conclusion that the algorithm will forcefully satisfy any input x in the circuit. $\endgroup$ – anony_std Nov 18 '20 at 15:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.