Ben
• Member for 9 years, 10 months
• Last seen more than a month ago
• Melbourne, Australia

The definition of the class NP-hard is that a problem is NP-hard if every problem in NP can be reduced to it in polynomial time. The definition of the class NP-complete is just the problems that are ...

Usually downcasting is what you do when the statically known knowledge the compiler has about the type of something is less specific than what you know (or at least hope). In situations like your ...

If it were this language: $B = \{\; 0^k1u10^k \mid k ≥ 1 \text{ and }u ∈ Σ^*\;\}$ you'd be in trouble. $B$ is not regular. The key problem is that when trying to recognise strings from $B$, you ...

The halting problem is undecidable of course. This implies that there is at least one program for which we cannot decide whether it halts or not. The undeicidability of the halting problem actually ...

You can construct a recognizer that simply simulates M on w and then simulates M on $w^R$. This will halt in finite time for all that are in A (by definition), and then you can accept if the first ...

A reduction from A to B shows that A is "no harder" than B in some sense. We call it a reduction because it reduces the problem of solving A to the problem of solving B. This is a usage of the word "...

It matters what is actually happening in the code. The following pseudocode is O(1) loop_factor = input() for x between 0 and loop_factor(): for y between 0 and loop_factor(): terminate ...

Reductions are useful in studying computability not so much to prove that problems are computable (although that is also done), but to prove that problems are not computable. Used to prove ...

I'm a little confused by your quote. There are two equivalent definitions of the NP complexity class in terms of Turing Machines: The class of problems for which a deterministic verifier exists ...

There are unfortunately as many techniques to prove functions uncomputable as there are to prove things in general, so there's no comprehensive doctrine for how you should approach this. Note that ...

No, it would be more powerful. The transition function would no longer be finite, and that buys you a lot of power. With an infinite alphabet, you can encode any input item from an infinite set in ...

I think most likely the explanation for some authors using "logic error" and "semantic error" interchangeably and some authors drawing a distinction is simply that they don't have a precise ...

A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not. Your ...

The condition that $y$ has length at least one is to avoid a triviality. If you allow the length of $y$ to be zero then for any language you can divide each word in the language into $xyz$, such that \$...

To elaborate slightly on the "it's impossible" statements, here's a simple proof sketch. We can model algorithms with output by Turing Machines which halt with their output on their tape. If you want ...

As spotted by svick, the first issue with the code in the OP is that names beginning with upper-case letters are variables in Prolog. So admit(CP) :- admit(AD) is equivalent to attend(X) :- attend(Y), ...

To be at all interesting (for the purpose of thinking about computability) a decision problem has to have infinitely many "yes" answers and infinitely many "no" answers. Such decision problems ...

An equivalent definition of NP is that it consists of all problems that are decidable (not just verifiable) in polynomial time by a non-deterministic Turing machine. NTMs are known to be no more ...

An interrupt is an "unusual" event that happens which needs to be processed immediately, regardless of whatever else is going on. I say "unusual" in quotes, because they're not necessarily unexpected ...

The basic difference between the C++ statement x = a + b and the Python statement x = a + b is that a C/C++ compiler can tell from this statement (and a little extra information that it has readily ...

I think your "non-trivial" property would need to be a property of sets of triples, not of triples themselves; i.e. you need that there are an infinite number of sets of triples that satisfy and do ...