@vzn I think that the presentation is about an hour...

@RespawnedFluff Are NP-complete problems a part of Computability Theory or Complexity Theory??

@MaryStar NP-complete problems are normally part of (Computational) Complexity Theory; the latter, together with Computability Theory is sometimes put under the broader umbrella of Theory of Computation.

The topic that I mentioned above, "Approximate solutions of NP-complete problems", is a part of Computability?? Or is it more related to Complexity Theory?? @RespawnedFluff

@MaryStar complexity theory

So would you advised me against this topic for the course Computability?? @RespawnedFluff

I think one is not offtopic:

It's a poor question -- a problem dump -- but offtopic is the wrong reason, isn't it?

@Raphael I think it is off-topic. Kinda like asking how to convert say a piece of Java to C++? How is that on-topic?

@Juho The principles of translating HPL to machine code are certainly are part of CS, aren't they?

My undergrad studies covered parts of this, and a compiler course in my masters more.

Of course we don't just want to translate the code -- that would be as bad as answering the mathematics question of solving a given recurrence.

Yes, I agree, but I don't think the question is concerned with principles or the general theory of translating C code to machine code

@Juho True, but I think we should be consistent. We keep boring, not-really-CS dumps of other subfields around because they are relevant for leaning how to do the interesting stuff. (All the stuff about asymptotics and recurrences, for instance.)

Mmh, true. By the way, should we be consistent and close (I suppose all!) questions of type "what should I ..." like this one here

it's an incredibly open-ended question, and you can tell by the answers that it really is opinion-based

I know that one in particular is from the early ages, but still

Hmm... I gotta go supervise an exam (wheee!), let's talk about that later.

Hehe, enjoy :-)

Hi, again. I was wondering if anyone here works on timed automaton?

I need help in proving there doesn't exist any timed automaton for the following language :

$L= { ((ab)^{k},\tau)| \tau_{2i+2} - \tau_{2i+1} < \tau_{2i} -\tau_{2i-1} \forall i \geq 1 }$

If anyone has any insights do tell me. I found it impossible to come up with an automaton for this using the timed automaton description. I wonder how I'd be able to conclusively prove that a timed automaton would not exist for such a language.

congrats WL et al, the Computer Science ad finally got to 6v & is now running on Theoretical Computer Science. go team!