User talk:CBM

m:User:CBM	Please leave new comments at the bottom of the page, using the "new section" button at the top of the page. I will respond on this page unless you request otherwise.	Archives 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

My ANI

It seems right that I tell you I closed the ANI you opened against me. I know this isn't the norm and is typically discouraged (partly why I am telling you I did it). My AWB rights are revoked, I am retiring and no longer editing and I think at this point everyone has said what they needed to say. There is no reason to take up all that real estate on the ANI page for what amounts to beating a dead horse. If you disagree feel free to revert my changes. --Kumioko (talk) 16:02, 25 February 2011 (UTC)

Does noncomputable imply PSPACE-hard?

this is not obvious to me. --Trovatore (talk) 23:26, 28 February 2011 (UTC)

Say A is a set in PSPACE; in particular A is computable by some index e. Then given a string s, we just need to determine whether program e will halt on input s and return 1. There is an index for a program i that halts if and only if this happens, and moreover an appropriate i can be uniformly computed from s such that its length can be bounded by a polynomial of the length of s as long as we have a reasonable Goedel numbering (this is a polynomial-time version of the s-m-n theorem). So there is a polynomial-time many-one reduction of A to the halting problem. — Carl (CBM · talk) 02:19, 1 March 2011 (UTC)

Oh, that I believe. But I don't see why just any noncomputable set should be PSPACE-hard, as you seemed to suggest in your edit summary. --Trovatore (talk) 02:24, 1 March 2011 (UTC)

That edit summary not really accurate. I doubt that every noncomputable set is PSPACE hard; I think it should be just an exercise using a Kleene-Post type argument modified to use polynomially clocked Turing machines. But I don't work with complexity theory much so I would have to check the details to be sure. In any case it seems like it should be false. — Carl (CBM · talk) 02:34, 1 March 2011 (UTC)

I think the answer is "unknown" since P ≠ PSPACE is an open conjecture (that everyone believes is true). If P=PSPACE then obviously every PSPACE problem is already in P without even needing the undecidable set. But intuitively, if every noncomputable set is PSPACE-hard, I think that means P^A ≥ PSPACE for a random oracle A, and that inequality looks obviously false, since it would give an immediate distinguisher between a cryptographic hash function and a random oracle, which "shouldn't happen" assuming P ≠ NP or some some slightly stronger version of P ≠ NP. I could also be plain confused about the whole thing. 71.141.88.54 (talk) 00:15, 4 March 2011 (UTC)

Article Tahash Timeline

Please look at the article Tahash, and on the Discussion Page: "Consensus on Timeline" give your opinion about the Timeline. Thank you. --Michael Paul Heart (talk) 12:42, 3 March 2011 (UTC)

Possible PR fix?

Hi Carl, I have noticed that occasionally there are PRs which have no PR template on the article talk page. This happened recently on a PR Finetooth opened and when I asked him about it, this is what he said.

It's possible to install (but not save) the PR template on an article talk page, to view it in preview mode, and to click through and fill in the rest of the form without remembering to save on the article talk page. I think that's what I must have done, and I think that's the process that accounts for similar glitches that we see from time-to-time at PR. This is a form of operator error rather than a flaw in the template design, but maybe a guru could make a doofus-proof template that would not work unless saved first.

Does this seem like anything that could be done for {{PR}}? I have also posted this on Geometry guy's page. Thanks, Ruhrfisch _><>°^° 14:23, 3 March 2011 (UTC)

I have one idea, but I need to test it some more. It's not straightforward to detect whether the page is in preview mode or is being viewed in regular mode, but maybe we can find a way to do it. — Carl (CBM · talk) 21:17, 3 March 2011 (UTC)