Ben
  • Member for 9 years, 10 months
  • Last seen more than a month ago
Are there problems in NP that do not reduce in polynomial time to any problem in NP?
3 votes

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 ...

View answer
Automatic Downcasting by Inferring the Type
3 votes

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 ...

View answer
Proving the regularity of a certain language
8 votes

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 ...

View answer
What is the amount of programs for which we can solve the halting problem?
Accepted answer
5 votes

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 ...

View answer
Undecidability of the following language
2 votes

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 ...

View answer
NP-complete reductions
Accepted answer
4 votes

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 "...

View answer
Input to make worst case on big O not possible?
2 votes

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 ...

View answer
Difference between reductions in algebraic problems versus reductions in computational intractability
1 votes

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 ...

View answer
Length of the certificate in complexity classes
3 votes

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 ...

View answer
What approaches are most useful when proving uncomputability of a given function?
7 votes

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 ...

View answer
Infinite alphabet Turing Machine
Accepted answer
18 votes

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 ...

View answer
Can all languages have semantic and logical errors?
7 votes

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 ...

View answer
A concrete example about string w and string x used in the proof of Rice's Theorem
Accepted answer
3 votes

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 ...

View answer
Length of mid part of the string in Pumping Lemma
4 votes

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 $...

View answer
Can constraint satisfaction problems be solved with Prolog?
9 votes

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), ...

View answer
How do you check if two algorithms return the same result for any input?
12 votes

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 ...

View answer
Is there an undecidable finite language of finite words?
2 votes

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 ...

View answer
Why isn't this undecidable problem in NP?
Accepted answer
11 votes

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 ...

View answer
What is meant by interrupts in the context of operating systems?
4 votes

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 ...

View answer
Can a dynamic language like Ruby/Python reach C/C++ like performance?
10 votes

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 ...

View answer
Non-trivial tractable properties of triples
Accepted answer
3 votes

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 ...

View answer
Is interaction more powerful than algorithms?
8 votes

Turning Machines model computation, and don't have a concept of interaction. In that sense a machine that supported interaction with an outside system can do things a Turning Machine can't. But the ...

View answer
What is the significance of context-sensitive (Type 1) languages?
3 votes

Many others have mentioned that Type-1 languages are those that can be recognised by linear bounded automata. The halting problem is decidable for linear bounded automata, which in turn means many ...

View answer