Yakk
  • Member for 7 years, 2 months
  • Last seen more than a week ago
  • Canada
If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?
24 votes

A few reasons, some generic and some specific. The generic reason is that this is a long-known famous problem which many smart people have tried to solve, and many smart people have gotten wrong. ...

View answer
Why, really, is the Halting Problem so important?
17 votes

You seem to be confusing the classic "self referential" based proof that the Halting problem cannot be solved with the Halting problem (aka Halt) itself. That self-referential program -- the program ...

View answer
Would proving P≠NP be harder than proving P=NP?
9 votes

We have not ruled out the possibility of a simple proof that P=NP. If someone tomorrow comes up with an algorithm that solves a NP-complete problem in P time, the world changes. On the other hand, ...

View answer
Why is the unit of image size not Pixel²?
Accepted answer
6 votes

The width of an image is being measured in a discrete 2 dimensional space. The image is 3840 pixels across. This means there is a horizontal band of 3840 pixels (which are each 2 dimensional regions)...

View answer
Why NFA is called Non-deterministic?
4 votes

Start off with a Finite Automaton. It has states and acceptance states and transitions. Now, give it more than one trasition rule of of each state, and say that it accepts if there exists a set of ...

View answer
How exactly is the process of showing a problem to be NP-Complete a proof by contradiction?
3 votes

What is NP A problem is in NP if, with a polynomial-length "magically provided" proof string for any given problem instance whose answer is "yes", can verify the answer is "...

View answer
Why do functional languages disallow reassignment of local variables?
2 votes

Optimizers in C++ turn traditional C++ code into static single assignment when it can. You can think of traditional imperative programming as chaining together functional steps. struct state { int ...

View answer
How can a computer deal with real numbers
1 votes

You are mistaking a map for the territory. The first thing to realize is that computers don't work on numbers. Computers work on bits and volts. We abstract that work on volts into working on bits, ...

View answer
What is the "description" of a Turing machine?
0 votes

A formal way to approach this is to note the existence of Universal Turing Machines. Let U be a universal turing machine. Then, for any other Turning Machine T there exists a tape state T' such that ...

View answer