[zaarn]

Re1: the problem here goes a bit deeper, classically the NP problem is a problem which requires a non-deterministic turing machine to solve. Ie a machine that can explore multiple outcomes at once, even the entire problem space to some extend.

A non-deterministic turing machine can interprete multiple instructions (write 5 to tape and go to state 2 OR write 3 to tape and go to state 19) and (depending on interpretation) use the instruction that gives the result fastest or explore all instruction branches at once.

Note that the "OR" in there is not a classical if-else, it means literally the machine can pick one. There is no memory value that tells it which is correct.

Basically, problems that are polynomial on a NDTM will likely be NP on a normal machine (with some exceptions depending on the problem).

Re2: As above, verifying is actually easy as you can then simply follow the execution branch the NDTM picked on a normal deterministic turing machine.

Atleast this above is what I learned in CS course 2nd semester.

[mortdeus]

I've read a little bit about turing machines and there is also a variation that includes what is called an "oracle" machine. Do you know anything about that?

[zaarn]

An oracle machine is usually a turing machine that can tell you things about other turing machines.

An example would be the Halting-Oracle, which can tell you if a program will halt or not without running it. (Of course, this oracle doesn't actually work since your program can have the oracle's output as input and simply do the opposite)

A NP/P Oracle might be an oracle that can tell you if a more efficient algorithm for your problem exists.

Such oracles can be setup to prove certain assumptions (or disprove) based on simply logical statements (see halting problem oracle above).

Oracle machines are also not really turing machines, it's usually assumed they can do the oracling in a single operation and they're usually a black magic box (there is no need to explain how they work, they're an abstract concept).