How does a co-NP problem differ from an NP (its complement) one? I have quite a hard time understanding co-NP problems.

If we can reduce every problem to decision problem. NP problems should accept YES instances -> instances where the answer is yes. So for example for Traveling Salesman problem, we would ask "Is there a path that visits every city, and is shorter than N" ?

For co-NP problem, they should accept NO instance -> answer to them is NO. But given this, how would we formulate co-NP problem to Traveling Salesman problem I mentioned earlier? if we formulate it "Isn't there a path that visits every city and is shorter than N"? If there wasn't the path, the answer would be YES -> so it would be YES problem, if the answer was NO, we would have to try the path which would be same as YES problem.

So what is the difference? Was my co-NP decision problem to said TSP correct?

I have read wiki and tried to find some sources but nothing helped...

Thanks for help!
A co-NP problem differs from its complementary NP problem exactly by being its complement! That's the whole story.


  NP problems should accept YES instances -> instances where the answer is yes.


I think you've confused yourself. Every problem, of any complexity, is a division of all possible instances into "yes" instances and "no" instances. For TSP, the "yes" instances are the maps where the salesperson can visit all the cities within the distance requirement and for co-TSP, the "yes" instances are the maps where the salesperson can't (i.e., the "no" instances of TSP).

What differs between complexity classes is the amount of resources and model of computation that are required to tell the difference between a "yes" intance and a "no" instance. For NP, we use a nondeterministic Turing machine running for a polynomial number of steps and say that the machine accepts if at least one computation path accepts, and rejects otherwise. For co-NP, we do the opposite: the machine rejects if at least one computation path rejects, and accepts otherwise.