Area 51 » Science

181

followers

Announcements

This is a proposal to explore whether it'd be useful to create a separate TheoryOverflow site dedicated to research-level questions in theoretical computer science, broadly interpreted to include algorithms, complexity, approximation, randomness, quantum, algorithmic game theory, computational geometry, computability, and the like. Please follow the discussion if interested, suggest examples for good and bad questions, and add your thoughts on whether or not such a site would be useful for the theory community. – Anand Kulkarni Jun 23 '10 at 2:38

What about type theorists, programming language semanticists, automated reasoners and the like? Are they all included? Similarly, George's point is a good one: compiler design and operating system design often overlap extensively with TCS. How wide a topic is theoretical computer science going to be considered? – Dominic Mulligan Jun 23 '10 at 11:47

My inclination would be to take a broad view of theory and encourage theory questions from these domains. The main criteria I'd use in deciding whether a question seemed suitable would be first, whether the question could be better answered on Stack or MathOverflow, and second, whether the question would be of interest to or answerable by the theory community. Suggest some sample questions from these areas! – Anand Kulkarni Jun 24 '10 at 8:12

show 4 more announcements

41 Example Questions (9 closed)

active oldest votes

up vote 21 down vote

added by Anand Kulkarni Jun 23 '10 at 2:21

MathOverflow presently supports questions of this nature that are oriented towards explanation and education rather than directed towards solving a specific research problem. Presumably, the asker would have a specific difficulty in mind they'd like to see resolved. – Anand Kulkarni Jun 23 '10 at 2:29

up vote 20 down vote

added by Anand Kulkarni Jun 23 '10 at 2:03

A reasonable answer could provide either a proof of undecidability, an algorithm for the problem, or some discussion of why the question is expected to be formally difficult. – Anand Kulkarni Jun 23 '10 at 2:23

up vote 20 down vote

added by Chris W. Rea Jun 23 '10 at 12:21

up vote 20 down vote

added by goldsz Jun 25 '10 at 0:41

I hope this is on topic, and that the plan isn't to just pose open research questions. – goldsz Jun 25 '10 at 0:44

Everyday expert-level questions like this that arise in the course of research seem reasonable to me, and MathOverflow has succeeded by encouraging exactly these types of questions. Hopefully nobody will simply ask for answers to questions that they know to be open without being more specific; as in MathOverflow's criteria (mathoverflow.net/faq#whatnot), the goal could be to obtain help with a particular approach in a specific context. – Anand Kulkarni Jun 25 '10 at 9:56

up vote 19 down vote

added by Chris W. Rea Jun 23 '10 at 12:18

Somebody voted "not a good example". Boooo ;-) – Chris W. Rea Jun 26 '10 at 16:12

Problems in NP are decision problems (i.e. yes/no questions). So hopefully the body of the question describes how to phrase "integer factorization" as a decision problem. – Douglas S. Stones Jun 26 '10 at 23:08

up vote 15 down vote

added by Robert Harvey Jun 24 '10 at 16:34

up vote 11 down vote

added by Jacques Carette Jun 24 '10 at 1:58

Why is this being considered an off topic question? It's a classic question in programming language design theory. – Dominic Mulligan Jun 24 '10 at 9:32

Indeed - I proposed it thinking it was on-topic. – Jacques Carette Jun 24 '10 at 11:48

My first reaction was that this was NOT a good question, but rather a simple Google query, which leads immediately to a Wikipedia page. But the WIkipedia page is particularly bad, which makes this a good question! – JeffE Jun 24 '10 at 15:56

Is there no good existing reference? I will remove my off-topic vote. – Robert Harvey Jun 24 '10 at 18:25

What "the expression problem" is keeps getting refined as people explore it. It is not really 'settled' (yet!). – Jacques Carette Jun 24 '10 at 21:53

up vote 11 down vote

added by JeffE Jun 24 '10 at 16:08

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPPI and SSISI. Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square. Is there a fast algorithm to determine whether a string is square, or is it NP-hard? (The obvious dynamic programming approach doesn't seem to work.) – JeffE Jun 24 '10 at 16:16

up vote 8 down vote

added by Jacques Carette, edited by Robert Harvey Jun 24 '10 at 18:34

I really don't see what this have to do with algorithms at all. The characteristics of such PL can be clearly defined, but advantages and disadvantages in PL are often of a subjective nature. – Daniel C. Sobral Jun 25 '10 at 17:11

I don't think this needs to have anything to do with algorithms as long as it's a legitimate question in the theory of program languages – Suresh Jun 25 '10 at 17:16

I agree with Suresh. Granted, a pl theorist who wants a flame war would say "decidable type checking" lets us actually run all good (well typed) programs, and thus "haskell is better than java", but despite that possible response theres some really cool math going on in analyzing these type systems, and thats pure theory :) – Carter Tazio Schonwald Jun 25 '10 at 22:54

I think 'is haskell better than java' is a good off topic question ;) – Suresh Jun 25 '10 at 23:05

@Daniel: This is TCS not algorithms. I considered this a legit question on programming languages. – Jacques Carette Jun 26 '10 at 21:21

up vote 7 down vote

added by Suresh Jun 23 '10 at 5:41

this is a reference request probably, but given the dizzying array of methods in this area, it's a good question to solicit expertise in (from one expert to another) – Suresh Jun 23 '10 at 5:41

up vote 7 down vote

added by Suresh Jun 23 '10 at 22:52

up vote 6 down vote

added by Jacques Carette Jun 24 '10 at 1:59

up vote 6 down vote

added by JeffE Jun 24 '10 at 16:22

	Believe it or not, this question is open. – JeffE Jun 24 '10 at 16:23
	There is a polynomial-time algorithm, via group theory, to decide whether the cube is solvable. – JeffE Jun 24 '10 at 16:24

up vote 6 down vote

added by Ryan Williams Jun 25 '10 at 16:35

up vote 5 down vote

added by JeffE Jun 24 '10 at 16:00

up vote 4 down vote

added by Anand Kulkarni Jun 23 '10 at 2:12

that's a bit borderline for a good post, on second thought. – Suresh Jun 23 '10 at 5:47

up vote 4 down vote

added by Roy Maclean Jun 24 '10 at 9:56

up vote 3 down vote

added by Roy Maclean Jun 24 '10 at 10:06

up vote 3 down vote

added by Akhil Mathew Jun 24 '10 at 15:40

up vote 3 down vote

added by Ryan Williams Jun 25 '10 at 16:22

Note: There could be multiple answers as there probably are several incomparable classes that satisfy the question. Knowing this antichain may be useful, though. – Ryan Williams Jun 25 '10 at 16:25

up vote 2 down vote

added by Anand Kulkarni Jun 24 '10 at 8:04

As posed, this type of question would be more suitable for MathOverflow. – Anand Kulkarni Jun 24 '10 at 8:05

it's a fine line. – Suresh Jun 24 '10 at 9:43

From the Area51 FAQ: Don't worry about whether a question might be asked on another site. Your goal is to make the best possible site for this community. – Robert Harvey Jun 24 '10 at 22:31

Good point! A better criteria might be whether such questions are suitably interesting for theorists; this one might be, depending on the context. Are there any better examples of suitably off-topic mathematics questions? Perhaps pure topology or analysis? – Anand Kulkarni Jun 25 '10 at 0:27

up vote 2 down vote

added by Roy Maclean Jun 24 '10 at 9:35

up vote 2 down vote

added by Roy Maclean Jun 24 '10 at 9:53

up vote 2 down vote

added by JeffE Jun 24 '10 at 16:01

closed as off topic by Anand Kulkarni, goldsz, user6092, SamiD, Ryan Williams Jun 25 '10 at 23:53

This question does not relate to the topic of the proposal.
It was closed as part of an automated migration of off-topic to close votes on September 29, 2011.

This is another good example of a question that would be too elementary, since it's covered by a suitable Wikipedia article / Google search. en.wikipedia.org/wiki/General_position – Anand Kulkarni Jun 25 '10 at 0:14

up vote 2 down vote

added by Ryan Williams Jun 25 '10 at 16:27

Every once in a while, a complexity theorist comes across a weird definition of a complexity class (where the languages must satisfy property BLAH if x is in the language, and property BLAH' if x isn't in the language). The community should be helpful in quickly determining where this class falls within the Complexity Zoo (qwiki.stanford.edu/wiki/Complexity_Zoo) – Ryan Williams Jun 25 '10 at 16:29

up vote 2 down vote

added by Martin Schwarz Jun 26 '10 at 8:48

up vote 2 down vote

added by Michael Jun 27 '10 at 17:18

up vote 2 down vote

added by incrediman Jun 28 '10 at 4:02

up vote 1 down vote

added by SamiD Jun 25 '10 at 19:18

	Sometimes the intuition behind an "established" belief is difficult to trace for a novice (or even a non-novice) so I think such a question should be on-topic even though potential answers are necessarily subjective in the absence of a proof, one way or the other. – SamiD Jun 25 '10 at 19:31
	could be a good community wiki-type question. alas I have no more positive votes to give. More voting, people ! – Suresh Jun 25 '10 at 19:40