« first day (2410 days earlier)      last day (2553 days later) » 

9:00 PM
@sehe I find it very limiting, almost insulting, that the physical world say we can't investigate 2^256 options.
 
Ell
@Fanael he didn't end it with a question mark
his full question was "can I ask you a question if graph reachability is NP-complete, does that imply NP is a strict subset of PSPACE?"
answer carefully :D
 
The title of the linked paper is " NP vs PSPACE"
 
It was an exam question, and I can't make my mind up. Because the space hierarchy theorem implies NL is a strict subset of PSPACE, and hence in the chain NL < P < NP < PH < PSPACE, there is at least one strict subset relation, and we ruled one of them out. If graph reachability being NP-complete would imply that NL = P (for whatever reason), then that statement is true.
 
fuck sake
 
user784668
@Columbo If graph reachability is NP-complete, then P = NP, because we know lots of polynomial time algorithms that solve it.
 
9:03 PM
I bought wrong brake shoes for my car
 
@Fanael That was the preceeding question (in that past paper), and I got that, yeah.
 
> "Proof by contradiction. Assume P=NP. Let y be a proof that P=NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P=NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction."
 
user784668
@Columbo I'm afraid I can't help you with this one.
 
@Columbo What a beautiful proof. There are two types of statements.
 
9:06 PM
@Fanael Hmm, that just makes it the more interesting. Thanks, anyway!
 
user784668
@Columbo Have you considered asking on cs.se?
 
1 - elegant, intuitive, and completely untrue.
 
@Columbo The thing is, it's more likely to figure out a way to reduce what was thought of as an NP problem into a P problem than to prove P=NP
 
@Fanael I kinda feel like a 3 mark question should be answerable without Stackexchange :/
 
@Columbo You just got a millon dollars
 
9:07 PM
2 - complex, derogatory, expensive and fully supported by management.
 
Dude what is it with help vampires in the lounge nowadays
 
also fucking carmakers
utilizing 1298540932 variations of the same part
for no reason whatsoever
god damn it
 
user784668
@Columbo But wait, isn't graph reachability NL-complete?
 
@Fanael It is indeed. Another past paper I had to do asked that :D
 
9:09 PM
Help vampires get directed to ask unclear questions in chat. They see victi people in lounge. They ask in lounge.
 
Doesn't help though, AFAICS.
 
What invectives are we allowed to use fighting these vampires?
 
Kill them with Kindness.
 
@Aaron3468 hold on there. This boundary thing is the lightness? he came back after a ragequit?
 
9:11 PM
Troll them to death
 
dammit
 
@Abyx Not the first time
 
so pathetic
 
@Puppy What about @rightfold, didn't he have another 20k+ SO account originally, and ragequit?
 
user784668
@Columbo So, if I understand it correctly, being NP-complete would also make it P-complete, because then P = NP, so NP-complete is exactly the same as P-complete.
 
user784668
9:12 PM
So NL = P = NP < PH < PSPACE then?
 
more than once I believe
 
@Fanael You have to be careful with the type of reduction. If we want to show that NL = P, any problem in P must be logspace reducible to a problem in NL.
 
@Abyx Just follow the link to Boundary's website. Or look for messages by Boundary in this room, and go to the last pages.
 
You reckon that P = NP implies any problem in P can be logspace reduced to a problem in NL? How does that follow from NP-completeness?
 
user784668
@Columbo Oh, right.
 
9:14 PM
P=NP <=> N=1
 
@Fanael Anyway, this is exactly why I investigated the question further, it was this kind of thought :-)
 
@Aaron3468 yeah, I should be blind not noticing that
 
user784668
@Columbo Honestly, I have no idea, I'd really recommend asking on cs.se.
 
user784668
@Columbo You're right, it doesn't, because we only know that any problem in P (and NP) can be reduced to graph reachability in polynomial time.
 
@Columbo In all likelihood, it probably indicates that some problems are computationally simpler than they appear to be. I highly doubt you've proven P=NP for any subset.
 
user784668
9:19 PM
If the reduction always needed linear space, then NL < P.
 
user784668
@Aaron3468 You don't need to prove P=NP here, it's assumed in the question.
 
That's true. I'm referring to the answer to the question. It's not uncommon for some problems to be reduced into a simpler method of computation.
 
0
Q: Does reachability being NP-complete imply NP being a strict subset of PSPACE?

ColumboDoes graph reachability being NP-complete (from which $\textbf{P} = \textbf {NP}$ follows trivially) imply that $\textbf{NP} \subsetneq \textbf{PSPACE}$? Or, for an equivalent problem, does it imply that $\textbf{NL} = \textbf P$?

@Fanael It's implied by the premise of the question, yeah.
 
user784668
Also what's the difference between cs.se and cstheory.se?
 
@Fanael Oh, there's cs.se?
lol
 
user784668
9:22 PM
 
Oh, okay. I just googled "complexity theory stackexchange" and got that.
 
user784668
CS by its nature is already theoretical.
 
or rather by name
 
cstheory seems to be for cs researchers. cs is for the already known facts
At least from what I understand
 
@Columbo there's also separate theoretical cs se for whatever reason
ok you found it already
 
9:24 PM
 
cs theory theory
 
Oh, wait. That's a different result, actually.
@Fanael Btw. do you know the "Nondeterministic memes for NP-complete teens" FB page? It's hilarious, you may like it
 
user784668
@Columbo I don't use FB much tbh
 
Shit, that link doesn't work.
user image
9
 
9:30 PM
lol, "NPCompleteTeens"
 
reposting to discord before it gets flagged
 
@Columbo Once again, you've either discovered a deep-reaching truth about the field in question, or you've discovered a fundamental flaw in the premise. In this case I think we can agree that it is the former.
Oh, hey, can I have the discord link? Mine expired when I got it the first time
 
@milleniumbug Why should it get flagged? For the word "porn"? The image has too low a resolution to be seriously NSFW-problematic IMO, but whatever
 
@Columbo don't ask me, ask flaggers
happens too often here
 
@milleniumbug flaggers are naggers
 
9:34 PM
 
@milleniumbug Okay, thank you. I'm Animu36. Can I be regular?
 
no.
 
9:51 PM
@Aaron3468 With enough laxative, anybody can be regular (or so the advertisements seem to imply, anyway--can't say I've really put it to the test personally).
 
pastebin.com/M573ueWi lol. but, hey, it works!
 
@JerryCoffin dunno, according to John Oliver nothing works for Orrin Hatch
 
@BoundaryImposition Just make sure you #undef those dirty macros when you're done playing with them.
 
@Aaron3468 mmm nah
:)
actually now that I'm C++11, with a bit of fiddling I could make these into functions (I think), if I can slot into into my inheritance tree somewhere to make sendMessage work
but meh
 
@Aaron3468 Next you'll be asking that he actually learn how to program!
 
10:00 PM
@Columbo the word porn in large type would make it nsfw in some places
 
@R.MartinhoFernandes Fair enough. Can moderators edit messages?
If not, I suggest.. ignoring the issue until it's too late. Works everytim.
 
@R.MartinhoFernandes Like the ISIS occupied Levant, if that is NSFW you should be worried about floggers rather than flaggers!
 
@Columbo They can edit to the extent of removing them (and so can room owners).
 
@JerryCoffin Sorry, I did mean room owners.
In that case, judge for yourself.
 
Moderation tends to lean towards censorship on a lot of sites. But mods here generally understand the difference between positive & politically incorrect versus negative & politically correct
 
10:29 PM
Yo, so does dropbox work in Red China? Its not syncing for one of my collaborators.
 
Apparently. A quick search shows that they'll need a VPN or a different filehost
But it's only a partial block
 
user784668
@Columbo: I see your question has been answered.
 
@Mikhail There's there was a workaround
 
@Fanael Verily. :-)
 
user784668
So it's possible that NL < P = NP = PH = PSPACE.
 
10:36 PM
Our university VPN looks blocked, I blame Bill Clinton for selling us out to the fucking Chinese
 
0
A: C++ printing pointer doesn't acknowledge showbase

BoundaryImpositionI propose that you cast to intptr and treat the input as a normal integer. Your I/O manipulators should then work. #include <iostream> #include <iomanip> using namespace std; int main() { void * n = (void *)1; cout << noshowbase << hex << reinterpret_cast<intptr_t>(n) << dec << endl; ...

pretty happy with this
nice bit of quick standardese parsing to distract from work
 

« first day (2410 days earlier)      last day (2553 days later) »