12:03 AM
@phwd er, no. Send yourself one?
I hope I did not make too bad a job on those two elementary questions.

@Raphael is that from SO? ISTR I answered that not so long ago
0

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) is not enumerable. That would mean that ...

Made it up because it is a major point of confusion year after year

No it's cool. I don't mind, I'm still trying to get a feel for the scope and what works. There are real questions I have, specifically stackoverflow.com/questions/3141927/… , I just want to make sure I ask the correct stuff before I really lay down the heavy things that I need to understand to get underway

6

Summary: total recursive functions are not recursively enumerable; the proof follows from a typical diagonal argument. “Recursively enumerable” is a property of a set of integers. “Partial recursive” or “total recursive” or “primitive recursive” are properties of functions from integers to integ...

@Gilles haha, I actually upvoted your answer then. :D If nothing comparable comes up, you can probably just c&p it?

12:08 AM
@Raphael not quite, you don't mention primitive recursive functions
I think I'll copy part of it though

Right, it is far too verbose for my question
remember to let others have a shot! ;)
as suggested by, uh, Victor I think.

@Raphael I haven't written many answers yet
relative to the number of questions, I mean

@Gilles You are active nonetheless. ;) But if you want to, go ahead. :)
yea, your U&L statistic is crazy

so having more questions than answers feels bizarre

It's not for long.

12:13 AM
dammit, I can't find a reference for the C preprocessor's maximum complexity

@Gilles So bizarre that you can't even write it correctly…

1

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free. How do I show the opposite, though? My TA has been adamant that in order to do so, we would ha...

0

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) is not enumerable. That would mean that ...

@StéphaneGimenez ?

You meant "having more questions than answers", didn't you?

@StéphaneGimenez hrhr

12:21 AM
@StéphaneGimenez you were saying? <whistles type=innocently>

That's cheating :p

"Congrats, you've gained the privilege – access to moderator tools" -- ohh, these guys are good, this feels like Christmas!

@Raphael only to lose them when we go public, unless you reach 2k rep by then

Congrats, and good night :)

@StéphaneGimenez Thanks, and good night too!

12:24 AM
@StéphaneGimenez Good night.

@Gilles Challenge Accepted!

or you might become a moderator, and you'll have access to even more tools

don't tempt me...

I'll leave the site if this guy becomes moderator.

@Gigili which guy? Why?

12:27 AM
@Gigili You better check your questions and answers. I edited more than one of them, and most of the time you agreed.

@Gilles Because just now feels like they're one of them - "we" don't want them, "we" do this, "we" do that, bla bla bla

@Gigili who's “this guy”? who's “them”?

The one you were talking to.

@Gigili Raphael?
you're awfully confusing

I prepared many questions to ask when I committed to the proposal - but now I cannot ask them.

12:30 AM
@Gigili of course you can!

@Gilles YES! who else you were talking to has gained the privilege?

@Gigili I don't understand you, seriously. Nobody did anything to you but you still keep lashing out?
@Shog9 Hah, now I know why my description of the parser tag did not come through! What was wrong with it?

@Raphael you can see that in your own activity history
@Gigili I'm still confused

@Shog9 And many other tag edits were refused, too. :-/

@Gilles I don't like how you react to my questions, first you told me "this obviously X, are you sure you wanted to ask this?" felt like I'm stupid, jerk and whatnot - Then that guy saying what an easy question .. Of course as a computer science graduate, I know less than someone who's studying master of CS.

12:34 AM
@Gilles I see, so I can dig for the reject reasons if I want. Not a very communicative interface, I'm afraid.
@Gigili So your ego got hurt. Happens. Get over it. Unless you can point to a comment that attacks you personally I do not see what you have to be angry about.

@Gigili You do seem to take everything as an affront. Don't be so paranoid! (And this is a security professional talking…)
When someone asks you to clarify a question, it's because they didn't know what you were asking. No more no less.

@Gigili This site is not about showing off who knows the most about CS - Raphael was just trying to help you focus that particular question, his intent was not to make you feel stupid.

@AlextenBrink @Gigili seconded. I have the tendency to be blunt, but if I want to offend you will know. ;)

@Raphael Congratz btw :)

@AlextenBrink Thanks! We'll see what good it will do. I guess you'll be next?

12:41 AM
It does look like it yes
@Gigili The main reason I'm active on this site is because I'd like to share things I know with other people - I've been a student assistant for a programming course not too long ago, for the same reasons

I see ...

@Gigili The people that asked me questions in that course had never programmed before in their lives
How can I say that their questions were stupid? They were not. I'm not sure what type of questions are stupid, but I can't really think of any easily

The main reason I was active was because I'll have a university entrance exam soon.

@Gigili So you have stuff to learn that we already know. Sounds like a good match to me?

When you think you're perfect or even more perfect than most of people, you'll think about other people as stupid unintentionally.

12:45 AM
Then don't hesitate to ask as many questions as you like on this site (provided they are on topic of course ;))

2

In our computer systems lecture we were introduced to the MIPS processor. It was (re)developed over the course of the term and has in fact been quite easy to understand. It uses a RISC design, that is its elementary commands are regularly encoded and there are only few of them in order to keep th...

0

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL library implements dictionaries (they call them maps) using (balanced) binary search trees, and ...

1

I foresee a number of topics that will probably come up again and again on this site in the future. As one has already been asked, I think we may want to come up with a policy for these types of topics while we're still in beta. The topic in question is 'how to determine the running time of an a...

1

We have two tags at the moment which seem to be the same topic. I think we should make one the synonym for the other. So my suggestion is to merge formal-grammars into grammars.

@AlextenBrink Context can make questions dumb. I have had a student asking the exact same question somebody else asked a few minutes earlier. This qualifies for "stupid", but not because of the content.

I can't speak for Raphael, but I definitely don't think of myself as perfect

@Gigili It is usually the opposite. The more you know, the more you know what you don't know.

12:46 AM
@Raphael Then the question itself wasn't stupid, but rather the fact that the student didn't pay attention
@Gigili I'll try to find an example where I felt stupid, that shouldn't be too hard...

@Gigili If you can accept that some of us may actually know what they are talking about we can get somewhere, I think.
@AlextenBrink true.

I asked that question after thinking about it for about half a year for a university course
It turned out to be trivially equivalent to some well-known and solved problem

@AlextenBrink Interesting

You can see that I felt stupid, as I commented that I wanted to delete the question
I didn't know all that much about SE back then though
Something I've learned over the years (mostly through bad experiences) is: chat is the worst means of communication ever invented
2
It is so incredibly easy to misexpress or misunderstand something

I like the variety of answers on this question
6

The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case? For example, it seems likely that a language that does not allow loops for instance, would be very easy...

Our different perspectives are apparent

12:51 AM
@Gilles So do I

It took me three weeks back then to wrap my head around this one. My friend teased me a lot.

But it may be a sign that the question was ill-directed?

@AlextenBrink maybe, and I think that's something we need to watch for here: there's going to be a varied audience

Anyway, I'm off to bed, it's been nice chatting with you guys, I'll see if I can think up more questions

Some of the CSTheory denizens need to step down several notches when the question is from a student or a programmer

12:53 AM
@AlextenBrink Good night! Oh lord, it's late...

@AlextenBrink Same as here, sleep well.

@Gilles I think high demands are fine, as long as we help people fulfill them.

@Gilles Indeed, but I think the same is true to some degree on SO, but through sheer volume this is possible not too apparent
*possibly

@Raphael it's not high/low demand, but we mustn't give too theoretical answers to questions from people who won't understand them

SO has lots of junk, unfortunately. Many non-experts seem to answer on stuff they don't grasp themselves (without knowing, of course), and the even more unknowing take it at face value. Hopefully, we won't get there.
@Gilles Right, agreed. Misunderstanding.

12:55 AM
I'm thinking of comments like this

@Gilles I thought you were talking about formulation of questions and answers to theoretical questions.

I'd never even heard of Parikh's theorem
@Raphael no, rather of answers to questions that come from students/programmers who aren't aiming for that much theory

Neither have I. I know what Parikh vectors/images are, so I could relate to some extent.

I'm off to bed too, good night.

@Gigili Good night!

12:56 AM
4

There are two settings under which you can get O(1) worst-case times. If your setup is static, then FKS hashing will get you worst-case O(1) guarantees. But as you indicated, your setting isn't static. If you use Cuckoo hashing, then queries and deletes are O(1) worst-case, but insertion is on...

http://stackoverflow.com/q/8115873

http://stackoverflow.com/q/3005161

http://stackoverflow.com/q/6446410

http://stackoverflow.com/q/5018064

http://stackoverflow.com/q/8323107

http://stackoverflow.com/q/711941

http://stackoverflow.com/q/8253118

http://stackoverflow.com/q/8318647

http://stackoverflow.com/q/303205

http://stackoverflow.com/q/2510485

http://stackoverflow.com/q/8399937

http://stackoverflow.com/q/8400943

http://stackoverflow.com/q/8426152

http://stackoverflow.com/q/8426246
^^^ @Raphael
Those are the questions where you left that "perfect for..." comment
@Raphael what's this now?

Oh, thank you! Let me check, I just now went through my activity list (bad timing).

http://stackoverflow.com/questions/9234966
http://stackoverflow.com/questions/8431127

Ah, I found it... The parser wiki edit looked fine, I suspect I intended to reject the excerpt. I reject a lot of tag excerpts - folks tend to make them too long without doing more than throwing in a definition. That's helpful mostly when the tag is potentially-ambiguous. Otherwise, try to keep it as short as possible, and include usage information where appropriate (this may only be needed later, as you observe how the tag is used).
For more, see:

@Shog9 What is what when?

Jeff Atwood on March 23, 2011

In the spirit of our recent redesign of the users page, we felt it was time to enhance the tags page, too.

As you can see, the tags page now shows a bit more information about each tag, namely:

The first three lines of the tag wiki excerpt for the tag. The number of questions asked in that tag over the last two relevant time intervals — day, week, or month. These intervals are also clickable so you can zoom into recent questions with the tag.

The number of questions asked in that tag over the last two relevant time intervals — day, week, or month. These intervals are also clickable so you can zoom into recent questions with the tag. …

1:05 AM
@Shog9 I understand. I tried to be about as verbose as other tag excerpts I have seen.

@Raphael Click the little arrow to the left - I was responding to you mentioning the parser wiki; didn't remember what you were talking about until I looked it up and saw I'd rejected an edit.

@Shog9 Ah, right, the chat does that. Lots of invisible features here. ;)

@Raphael Full of surprises... BTW: if you see a question that was well-answered on SO and you'd rather not re-post it here, feel free to flag it and ask a moderator to review.

@Shog9 shouldn't we wait a bit before migrating questions?
at the very least until the public beta!

@Gilles Uh, I'm not suggesting any of these get migrated
2 hours ago, by Gilles
I had a little chat with Shog9, and he encouraged us to repost old CS posts from SO/Math/ProgSE that got no love (closed, or unanswered, or only crap answers

1:10 AM
@Shog9 so what do you suggest doing on CS questions that did get a good answer on SO?

Repost, not migrate. And only if they're not doing well where they are
@Gilles If it got closed, ask for a review
(re-open)

ah, ok

Sorry, I just got home, jumping back into a conversation that probably wasn't active

1

When reporting algorithmic complexity of an algorithm, one assumes the underlying computations are performed on some abstract machine (e.g. RAM) that approximates a modern CPU. Such models allow us to report time and space complexity of algorithms. Now, with the spread out of GPGPUs, one wonders ...

I'm off to bed now, too. Far too late again! See you, good night.

1:42 AM
1

It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even not recursively-enumerable. Between these two types are the recursive non-context-sensitive langua...

3 hours later…
4:28 AM
0

At the midterm there was a variant of the following question: For a decidable $L$ define $$\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}$$ Show that $\text{Pref}(L)$ is not necessarily decidable. But if I choose $L=\Sigma^*$ then I think $\text{Pref}(L)$ is also $\Sigma^*... 0 Let$\cal{S}=\{S_i\}_{1\leq i\leq n}$be a partial$(m,k)$-design and$f: \{0,1\}^m \to \{0,1\}$be a Boolean function. The Nisan-Wigderson generator$G_f: \{0,1\}^l \to \{0,1\}^n$is defined as follows: $$G_f(x) = (f(x|_{S_1}) , \ldots, f(x|_{S_n}) )$$ To compute the$i$th bit of$G_f$we take... Does anybody have a question relating basic A.I.? 2 hours later… 6:19 AM 0 Originally: http://math.stackexchange.com/questions/74453/how-is-the-loop-invarient-obtained-in-this-square-root-bound-finding-algorithm but unanswered Consider the following algorithm. u := 0 v := n+1; while ( (u + 1) is not equal to v) do x := (u + v) / 2; if ( x * x <= n) u :... 6:47 AM 0 How do I prove that the Toffoli gate is universal? 0 Originally http://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there The BNF is defined as followed: S -> aAb | bBA A -> ab | aAB B -> bB | b The sentence is: aaAbBb And this is the parse tree: Phrases: aaAbBb, aAbB, bB Simp... apparantly our proposal is still getting most number of followers on area51 which makes it the hottest proposal on the site 7:15 AM at this rate there will be more followers than comitters which has never really happened on a launched SE site before in history of area51 AFAIK 8:11 AM 0 Re-posting from cstheory as suggested I'm a graduate student taking a course in theory of computation and I'm having serious trouble producing content once I'm asked to. I'm able to follow the textbook ( Introduction to the Theory of Computation by Michael Sipser ) and lectures; however when as... 1 hour later… 9:14 AM @RanG I have absolutely no knowledge in AI. :-/ 9:44 AM @KenLi Interesting. To some extent, this is to be expected. Many people active on SE may have a latent interest in CS. Now they see the site hit beta (because it is hot) they start pushing buttons; committing is no longer possible, so they follow. At least, this is one explanation. A more pessimistic one is that many people are not ready to commit because they are no "experts" but want to use the site for their questions; this may be a good or bad thing. 10:30 AM 2 When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are there any advantages of one over another? The ones I could think of: If you expect your data to be... 11:24 AM 0 Our professor asked us to think of a function in OCaml that has the type 'a -> 'b i.e. a function of one argument that could be anything, and that can return a different anything. I thought of raise, but the professor said there was a solution that doesn't require any function in the stand... 11:55 AM 0 Accordint to this article$P \neq NP$http://arxiv.org/ftp/arxiv/papers/1111/1111.0305.pdf But.. I know that is not a real demonstration. The idea is quite simple: a variation of TSP. What is the route (with weights included) with a lowest lexicographical order after the strings represen... Hey, who broke MathJax? 12:17 PM @Gilles did! No idea, really. I am bugging the higher-ups over in the mod chat about that. does it work for you on other sites? It might be a problem with the CDN; overall response is slow. in The Assembly, 1 min ago, by Sathya No, don't despair! We're going to repair! RT @marcgravell: Yes, yes, we know! #stackoverflow This might be interesting for chat newbies like me: meta.stackoverflow.com/questions/57286/… 17 There is special linking to some sites in chat. What is the full list of supported and integrated sites? And mathjax.org seems to be down as well. 12:53 PM 0 I remember coming across the following question about a language that's supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question? Anyway, here's the question: Show that the following language is context free$\{xy | |x| = |y| but x\n...

1:19 PM
20

Screenshot Use /command shortcuts to perform common chat tasks: See message history inline: Easily preview replied-to messages: And much, much more... About Legends tell of a prolific Meta Stack Overflow chatter who despised using their mouse above all things. In an effort to keep t...

this is useful

2

It was bound to happen and thankfully, it did now rather than later: we received the first question about a claim regarding P?=NP. Some topics, in particular this, attract lots of public attention and laymen research. I do not want to belittle such efforts, but according to experts (i.e. complex...

We're experiencing some unexpected downtime. We're investigating. Sorry for the inconvenience.

2:17 PM
1

In Hromkovič's "Algorithmics for Hard Problems" (2nd edition) there is this theorem (2.3.3.3, page 117): There is a decision problem $P$ such that for every algorithm $A$ that solves $P$ there is another algorithm $A'$ that also solves $P$ and additionally fulfills $\qquad \forall^\inft... 0 I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web: /\*((!\*)*\*+(!*|!/))*((!\*)*\*+|(!\*)*\*/ However, as you can see, this is a rather messy expression, and I have no... 2:44 PM 0 I remember I didn't have this problem before, but now I refreshed the page trice but the LaTeX part isn't shown properly. 2:59 PM Do you have the same problem? Ello, BTW. @Gigili I don't see a problem, what do you mean? I cannot upload image The toolbar is empty. @Gigili I see, of course; jup, same here. "Error: The connection to ws://sockets.ny.stackexchange.com/ was interrupted while the page was loading. Source File: http://cdn.sstatic.net/js/full.js?v=664ef139404d Line: 6" probably Apparently the problem is related to MathJax not working - it seems to affect all SE sites that use MathJax. (and only those) @sepp2k Yes, but the toolbars are not related to MathJax? Btw, congratulations @Gilles to 1k! 3:10 PM Right, but the toolbars work on sites that don't use MathJax (like Stack Overflow, code review,...), but do not work on sites that do use MathJax (us, cstheory, math.se). So somehow the MathJax problems must have messed up the toolbars. @sepp2k I see. 0 I was about to ask a question but the toolbar is gone and I cannot upload the image to post the question. It's not the case on other SE sites, not even in meta.CS. @Gigili I am sure the techs are aware of that; in particular, I posted into mod chat. They can't do much anyway, as they have to wait for mathjax.org to come back on. @Raphael Thank you. 3:32 PM @sepp2k Is there a way to post an image in my question? @Gigili You can upload it at imgur.com manually and create the code manually (copy from another post) @Raphael Great, thank you. @Gigili Welcome. MathJax is back on! 4:06 PM 1 I came across this figure, expressing that context-free and regular languages are subset of efficient problems. I perfectly understand that efficient problems are subset of undecidable problems because we can solve them but it could take a very long time. Why are all context-free and regular lan... 4:30 PM @Gigili I edited your question 315 quite heavily. Please check that I did not distort what you wanted to say 1 I was reading an article that described the switch between user-space and kernel-space that happens upon a system call. The article said An application expects the completion of the system call before resuming user-mode execution. Now, until now I was assuming that some system calls are bl... 2 This question related to writing titles and editing posts. It is well-understood that titles should be expressive and tell about the content of the post, i.e., about the specific question being asked. Along these lines, should we encourage having latex in the title, or ASCII (or, wording) approxi... 4:50 PM @Raphael "heavily" is the word there! I don't know how to show you, it's a power point presentation from my automata course, @Gilles. @Gigili Your wording seemed very uncertain to me and I wanted to phrase your question in a more assertive way. Thank you @Raphael, I appreciate your effort to keep site perfect. I agree with the whole edit except some minor parts. @Gigili I'm glad! Feel free to change back parts where you think I misunderstood. I can upload it for you if it's important @Gilles. 5:31 PM 1 I am reading about atomicity and came across the following scenario int x = y = z = 0; Thread 1 Thread 2 --------- -------- x = y + z y = 1 z = 2 Which gives the following sets of output $$\begin{array}{ccc}1&2&3\\ T1 : x = y + z&T2 : y = 1&... @ComputerScience Too late! 5:58 PM 0 Is it not necessary to encode both the uppercase and lowercase letter while encoding a message with the move-to-front transform? From an old computer science course exam, the problem was to encode Matt_ate_the_mat starting with an empty list. Using the author's solution methodology of not taking... 6:29 PM 1 Here is the standard pseudocode for breadth first search: { seen(x) is false for all x at this point } push(q, x0) seen(x0) := true while (!q.empty()) x := pop(q) visit(x) for each y reachable from x by one edge if not seen(y) push(q, y) seen(y) := true Here push and pop ... @Gigili it's not vital, and “presentation from my automata course” already helps Good crop today, I'm out of votes 7:11 PM why is the theme for CS.SE so different from the usual 'sketchy' theme used on other betas? the "something-is-different-on-the-internet-be-angry" part of me is acting up because of it @ArtemKaznatcheev It's the new beta theme. All new betas will have it (and I believe the old ones will adopt it soon as well) oh no! change! unacceptable! I've grown fond of the old sketchy theme Robert Cartaino on March 06, 2012 I wanted to give you a quick look at the new Stack Exchange Beta theme. Yes, we are retiring the familiar “Sketchy” theme and rolling out a more-polished and finished design for the beta sites. Raise the curtain, cue the trumpet fanfare… Alas, poor Sketchy… Over the course of the next few weeks, we will be rolling out the new Stack Exchange Beta theme to all the sites still in beta. At first glance, the new beta theme looks like an unembellished version of any graduated site: Finished, but without any particular “beta” theme, per se. But that’s sort of the point. … I actually prefer the new design to the sketchy theme. And I'm as resistant to change as anybody. Ahh, I see thanks for the answer @sepp2k ! No problem 7:24 PM @ArtemKaznatcheev Could you explain your disagreement about the P vs NP question? And why did you answer if you also voted to close? 7:47 PM Sure thing @Gilles I think the question is a NARQ because it basically asks too much of the person answering and because it does not show that the OP did much thinking on the question I answered the question just because I was trying to distract myself from doing actual work and clicked on the paper to see how badly formatted it was since one of the comments suggested that I usually know where the arguments in these papers break down and so I just scrolled to the relevant section and copy and pasted the part of your answer on meta that I disagreed with is in how one should proceed in editing the question The question is fundamentally about P vs NP the OP just doesn't have enough background to know which part of the proof to pay attention to and thinks that novelty in a P vs NP argument will come in the definition of the problem while the novelty and errors and difficult-to-prove parts usually come in establishing the lower bounds thus, if you rewrote the question as "is hashed TSP in P?" the answer you would get is "no, it is coNP-complete, and thus probably not in P" which would not help the OP at all. @ArtemKaznatcheev we're going to have lower standards on CS than on TCS. The typical standard for research on most SE sites is having read the Wikipedia article (and even that is sometimes debated) of course @ArtemKaznatcheev this is where I start to disagree The asker asked a large question, some parts of which are off-topic or otherwise unwelcome My general practice in this case (and I've seen it elsewhere on SE) is to strike off the parts of the question that are off-topic or to reword them to make them more useful to the asker if it can be done @Gilles Well, I guess then I disagree with you on a matter of personal opinion (i.e. what the question is about). I would rather close the question and have the OP ask a new question like "Is hashed TSP in P or NPC?" here, I don't see any way to salvage the question other than restricting it to the specific problem he spelled out If I have to read the article in order to edit the question, it's too much 7:57 PM @Gilles I agree on rewording if it preserves the spirit of the question, but that is where we seem to disagree @ArtemKaznatcheev but he did ask about this specific problem he also asked about does this prove P vs NP and where is the mistake if we take him at face value (and I see no reason to do otherwise), he read the paper, and stumbled on one difficulty so we should answer about this difficulty and if anyone has advice regarding the rest of the paper, it's nice to mention it, but don't treat it as part of the question The question says "This is clearly in NP (the decisional problem is: Is there a hashed string smaller than w? Checking this is polinomial, right?); the article says it is not in P. Maybe here is the problem? Is this a real proof? Where is the error?" so he is asking "can we prove this question is not in P?" at face value anyways, you and I don't have to agree on interpretations of the OPs intent or question. If my answer is low quality, wrong, or out-of-scope then please downvote it or comment on it to let me know. Oooooh I think I see He's claiming that some variant of TSP is not in P This is an extraordinary claim, requiring extraordinary evidence and all he's providing for evidence is some random article on the web Right. On these grounds, I agree with the closing. 8:01 PM well, he is claiming a proof of some variant of TSP being OUTSIDE of P or asking about such a proof but that is equally extraordinary claim since that is a question TCSers have worked on for nearly 40 years now @ArtemKaznatcheev yes, I'm on a roll for leaving out negations today, sorry @Gilles Haha, I do that all the time. No worries. The thing I AM worried about though is answering an off-topic question. I know that on cstheory.SE that is considered to be a nono So maybe I should withdraw my answer... but seeing an 'answer' (which really should have been a comment) already on the question made me follow suit @ArtemKaznatcheev I've voted to close and edited my meta answers thanks for your help in making me understand what the question was really asking 8:23 PM @Gilles no problemo! I up-voted your revised answer. Hi everyone. I have a small question which I am kinda ashamed to ask on the meta site. go ahead but don't be ashamed of asking questions Sorry, I pinged out. So, is it appropriate to ask questions I already know the answer to? @Daniil sure, it is. It's even linked from the site FAQ: Jeff Atwood on July 01, 2011 The FAQ has contained one key bit of advice from the very beginning: It’s also perfectly fine to ask and answer your own question, as long as you pretend you’re on Jeopardy! — phrase it in the form of a question. So … if you have a question that you already know the answer to if you’d like to document it in public so others (including yourself) can find it later it is OK to ask, and answer, your own question on a relevant Stack Exchange site. To be crystal clear, it is not merely OK to ask and answer your own question, it is explicitly encouraged. … Just be sure that the question you're asking would be useful to someone else, either because you needed to do some research to answer it, or you heard it and the answer from someone else, or you had that question at some time in the past Oh, cool. 8:38 PM we have a few questions on seeding advice on the meta Yeah, I checked meta out, but I didn't manage to find any consensus So, this question is Ok, right: cs.stackexchange.com/questions/333/… ? 5 It's 6 days into the private beta, we only have 66 questions, and Robert Cartaino has very discreetly announced: We decided to extend this private beta another 7 days. The question count is a bit on the low side to launch and that gives you a bit more time to flesh out the scope and let the c... ^^^^ this one in particular you can bet that I knew the answer to this but there was a time in my life when I didn't :) @Daniil looks ok, but doesn't the wikipedia article answer your question? we don't have any difficulty requirement, but duplicating Wikipedia isn't useful of course, if you think the WP article is unclear, asking for clarification is fine, but you should say that you've read it and what you didn't understand Or am I misreading your question and is it asking for something different? Ah, true. No, you are completely right. 8:47 PM 1 Note: This is a seeding question and might have appeared on StackOverflow before. (Feel free to close if you think it is inappropriate). You are given an array of 2n elements$$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$The task is to interleave the array, using an in-place algorithm such ... posted on March 13, 2012 by Daniil I've read that deterministic Büchi automata and non-deterministic Büchi automata, unlike DFA and NFA, do not recognize the same set of languages. Since every deterministic Büchi automata is also a non-deterministic one, I thought that the class of languages, recognized by it is a subclass of languages, recognized by non-deterministic BA. How do I prove that it is in fact a str I've voted to delete the question, but it seems to persist there. @Daniil no, it's deleted, that's why the feed bot didn't find the tags and author No, it's deleted. Pardon me, perhaps it was cached in my browser. @Daniil is there something you think is missing or unclear in the WP article? Duplicating WP is useless, but complementing WP is great 8:52 PM Not really, I actually understand it. I'll try to think of more questions tomorrow. Thanks for helping. 9:17 PM 0 In some other communities, there have been discussions about the use of the "Community wiki"-function. The policies seem to differ from site to site, so before it comes to any problems here about what should be CW'ed and what should be deleted: What is our stance? References: The Future of Co... I'm finding it very hard to come up with interesting questions that can't be solved by 10 minutes of Googling... @sepp2k take a textbook, read the first few chapters, ask about a point you find unclear, or one of the exercises are you a student/teacher/researcher/programmer/other/decline-to-say? I'm a student. so ask about something you didn't understand in class or in a textbook or, we're aiming for more elementary questions, so something you didn't understand in an earlier class or take a CS question that got a bad reception on SO (bad or no answers), clean it up if necessary and repost it 10:11 PM 0 Suppose the datatype for a BST is defined as follows (in SML) datatype 'a bst_Tree = Empty | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree; So there are two cases one in which the BST is Empty or it can have a (key,value) as well as two children. Now, for the case of an AVL where the con... 1 I asked a question that has a tricky answer, which I saw explained in some dark corner of the Internet a long time ago. I did so after seeing another question that was posted by someone who knew the answer, just to seed the site with interesting content. The response, a highly voted comment "thi... 1 hour later… 11:37 PM About you question @Gilles, I think both$U(N)$and$D(N)$tends to infinity so you cannot define a ration. @Gigili this doesn't mean you can't define a ratio for example you can compare, say,$x+3$and$\sqrt{x}$asymptotically. Or$e^x$and$e^{x^2}$. Or$x + \mathop{sin}(x)$and$x$. etc Ratio* Umm, well I meant what jmad said, not computable As you cannot say there are$P(N) problems

even if they aren't computable, we might know something about how fast they grow
In principle, given a particular syntax, we can enumerate all the well-formed programs of length N and manually determine whether they are decidable

I don't think so

So the number is mathematically well-defined
I have no idea if anything is known
for all I know this is a very difficult open problem
or maybe it's a consequence of some general theorem in complexity theory

11:51 PM
What I know about decidable and undecidable problems is , the former says the can be solved but "it could took a very long time but the latter says we cannot find solutions in any finite amount of time. So it doesn't make sense to say from every 10 problems, eight of them are decidable and the rest are undecidable.
At least I think so.

@Gigili it does make sense. It's something that a human can determine (in principle — assume an infinitely clever human). It's not something that a machine can determine in general.

And there's no paper or research done about it, at least I didn't find any
As long as we don't know how many problems we have, how we can define something like a ratio?

oh boy, I have to get up in 4 hours, and I'm stuck trying to inverse a permutation
@Gigili we can define it. It may be very difficult for us to compute, but we can define it.
In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that informally represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin. Although there are infinitely many halting probabilities, it is common to use the letter Ω to refer to them as if there were only one. Because Ω depends on the program encoding used, it is sometimes called Chaitin's construction instead of Chaitin's constant when not referring to any specific encoding. Ea...

Me too, I have to get up at 6 but it's 4 and I am here!
Well I'll catch you later @Gilles, good night for now!