Area 51 » Science

definition commitment beta

25 Example Questions (2 closed)

active oldest votes
up vote 10 down vote
The subset sum problem is NP-complete. Can the following variation be proved to be NP-complete?
added by Ken Li, edited by WikiSpeedia hang-around Nov 23 '11 at 20:26
link
up vote 10 down vote
Is this algorithm O(N) in worst case?
added by Ken Li Sep 27 '11 at 4:11
link
Based on cstheory.stackexchange.com/questions/6096/… which was also closed as off topic on TCS. – Ken Li Sep 27 '11 at 4:12
up vote 10 down vote
How can I formally show that my algorithm terminates?
added by Raphael Sep 29 '11 at 22:20
link
up vote 10 down vote
How fast can you multiply matrices and are the algorithms practical?
added by Raphael Sep 29 '11 at 22:22
link
up vote 10 down vote
How can you convert an ambiguous CFG into an unambiguous one?
added by Raphael Sep 29 '11 at 22:25
link
up vote 10 down vote
Is it possible to enumerate all propositions entailed by a set of formulas in higher-order logic?
added by Gilles Oct 2 '11 at 22:03
link
up vote 10 down vote
Is every context free language over a unary alphabet regular?
added by Gilles Oct 2 '11 at 22:45
link
Asked (not very well) on Stack Overflow and closed there. – Gilles Oct 2 '11 at 22:45
up vote 10 down vote
What is a mostly-concurrent garbage collector (as opposed to a concurrent GC or an ordinary incremental GC in a concurrent system)?
added by Gilles Oct 2 '11 at 22:50
link
Asked on Stack Overflow and unanswered there. – Gilles Oct 2 '11 at 22:50
up vote 10 down vote
I read that modern CPUs predict targets of conditional jumps. Why does this make sense in principle and how does it work?
added by Raphael Oct 3 '11 at 6:44
link
up vote 10 down vote
What other mechanisms besides the Pumping Lemma are there to prove a grammar is not regular?
added by Daniel A. Oct 15 '11 at 16:55
link
1  
I like this question. How to determine the regularity of languages is a question that often arises on SO, usually doesn't receive a proper answer, but is far too basic for TCS. – danportin Oct 16 '11 at 4:23
up vote 5 down vote
How can I avoid premature convergence to a local optima on my genetic algorithm?
added by Ken Li Sep 27 '11 at 4:13
link
up vote 5 down vote
How costly is case insensitive search as compared to case sensitive search?
added by Gilles Oct 2 '11 at 21:53
link
This topic sounds like something that'd be better asked on SO. Fully understand there is a CS way of reading this, but that subject line doesn't really emphasize that. It also involves a lot of non-theory stuff ("case insensitive" is complicated) – derobert Nov 30 '11 at 7:31
@derobert The full question where I encountered it in the wild was whether case insensitive search is exponential in the number of letters, because abc could be any of ABC, ABc, AbC, etc. That's an (elementary) algorithmic question, which would work on SO but is more about science than about programming. – Gilles Nov 30 '11 at 21:37
up vote 2 down vote
Is the emptiness problem for one-way nondeterministic stack automata solvable?
added by danportin Oct 12 '11 at 9:00
link
up vote 2 down vote
What is the difference between NP-hard and NP-complete?
added by Richard, edited by WikiSpeedia hang-around Nov 23 '11 at 20:24
link
up vote 2 down vote
Would the A* search algorithm be better for a hexagonal based map or Dijkstra's Algorithm?
added by Richard Oct 19 '11 at 20:45
link
up vote 1 down vote
Would the Branch-and-Bound algorithm be useful for the Traveling Salesman problem?
added by Richard Oct 19 '11 at 20:39
link
up vote 1 down vote
What is the best way to use a depth-limited search for an AI using a geo-spatial coordinates system?
added by Richard Oct 19 '11 at 20:48
link
up vote 0 down vote
Is the Post Correspondence Problem over a unary alphabet decidable?
added by danportin Oct 12 '11 at 8:41
link
up vote 0 down vote
Does every set of definite clauses have a least Herbrand model?
added by danportin Oct 12 '11 at 8:46
link
up vote 0 down vote
Is there a linear time algorithm that decides whether a symbol in a context-free grammar is nullable?
added by danportin Oct 12 '11 at 8:54
link
up vote 0 down vote
What were the errors in Vinay Deolalika's proof that P ≠ NP?
added by Richard Oct 19 '11 at 20:33
link
I feel such a question should go to cstheory.SE. But then it might get closed there because of "crank" associations. (Btw, only call it "proof" if you are convinced it is valid.) – Raphael Oct 19 '11 at 22:22
Proof, as in "formal proof". A proof can have errors and be invalid. – Richard Oct 20 '11 at 18:45
@Raphael, it already exists on cstheory.SE =). This question could go on both sites, but we have to be careful of post-crosting. – Gopi Oct 27 '11 at 13:48
up vote 0 down vote
When did the "science" in computer-science first appeared? [closed]
added by Gopi Oct 29 '11 at 13:22
link

closed as off topic by Ninefingers, Dori Nov 5 '11 at 0:20

This question does not relate to the topic of the proposal.
up vote 0 down vote
Which of the forms of notation used for big-O (O, big theta, little theta...) are we actually using when we talk about the run time of an algorithm?
added by Ninefingers Nov 4 '11 at 18:26
link
asked slightly differently on SO and is probably out of place, although answered, there. stackoverflow.com/questions/471199/… – Ninefingers Nov 4 '11 at 18:26
up vote -2 down vote
Why is HTML not a regular language?
added by Ninefingers Nov 4 '11 at 18:34
link
Based on the somewhat famous SO question (stackoverflow.com/questions/1732348/…) - might be too open ended though. – Ninefingers Nov 4 '11 at 18:34
5  
How is it open-ended? If you take a specific version of HTML, it's a formal language. And it should be easy to prove that that language is not regular using pumping lemma. – svick Nov 8 '11 at 14:18
up vote -4 down vote
If you have a class template header in C++, how do you define its member functions its respective .cpp file? [closed]
added by Ken Li Oct 8 '11 at 1:38
link

closed as off topic by Mark Trapp, svick, Richard, Dori Oct 20 '11 at 8:35

This question does not relate to the topic of the proposal.

2  
I suggest this would be perfect for Stackoverflow. – Marcin Oct 13 '11 at 13:53
It is a proposed off-topic question – Ken Li Oct 19 '11 at 22:01
3  
Area 51 does no longer work that way, Ken; we are supposed to collect only on-topic questions. – Raphael Oct 19 '11 at 22:25