« first day (875 days earlier)      last day (4082 days later) » 

user1357851
2:00 AM
generally O(N) linear speed is the best speed you can hope for
 
NP -- the set of all problems we can verify a solution for in polynomial time
We know that any P problem is NP
because we can always verify a problem by just finding the solution independently
 
@nneonneo ?
 
sorry, what's confusing?
 
I didn't know that, seems weird.
 
@nneonneo calling it "reduction" has always confused me - if you can only reduce to a problem that's harder or equally as hard, it's hardly reducing our problem :p
 
2:01 AM
yeah, so mathematically P is a subset of NP
@melak47: yes, "reduction" means you always reduce to a problem that is at least as hard.
on the flip side, it means that if we solve any NP-complete problem in polynomial time
then we use that chain of reductions to solve every NP problem in polynomial time
 
@melak47 You basically show that for any given problem of type X, you show that you can solve it by solving a problem of type Y.
 
why's that? NP-complete is defined as the subset of NP problems to which any NP problem can be reduced.
 
@Mysticial I know :)
 
@nneonneo Ah that's clearer.
 
let me rephrase: if you have any problem in NP, then you can somehow reduce it to a problem that is NP-complete
and consequently, NP-complete problems must be, in some sense, the hardest problems in the whole NP class
 
user1357851
2:04 AM
I think I am off to some more meaningful deployment (continue my Android app :p)
 
because if we could solve any one of those easily, we'd solve the whole lot (but nobody, ever, has managed to do that yet)
NP-hard, by the way, means any problem to which you can reduce an NP problem
 
so lets get on the bomb dropping for great success!
 
so you can reduce an NP problem to anything that is NP-hard
but NP-hard doesn't restrict itself to NP, so that's like saying you can reduce any problem to the halting problem
 
Some examples would be nice :)
 
yeah, I konw
I'm trying to recall any nice examples of reductions from class
 
2:05 AM
graph coloring?
traveling salesman
 
TSP is kind of cool
but reducing e.g. 3SAT to TSP is totally nontrivial
 
I'm most familiar with graph coloring since it's used for register allocation.
 
you can reduce some P problem to TSP for fun, I guess...let's see
 
heh, for fun :p
 
well, OK, here's an easy reduction
the problem of detecting if a graph is bipartite is in P
 
Xeo
2:06 AM
If a graph is what?
 
@nneonneo You're gonna have to explain bipartite.
 
That's a complicated term.
 
right
are you familiar with graphs in general?
nodes, edges, etc.?
 
Xeo
aye
 
2:07 AM
Basically if you can color a graph with only two colors and no two nodes connected nodes have the same color.
 
ok
 
There's this in SO.
 
@nneonneo Bipartite is poly right?
 
yes
 
It's 3 and up that's NP-complete.
 
2:08 AM
right
calculating the chromatic number of a graph -- the minimum number of colours you need to colour it -- is NP-complete
 
Xeo
Wait.. what is that colouring all about? :)
 
@nneonneo verifying that number is poly? or non-poly?
 
well, a proof of verification is the colouring
which of course can be verified in polytime
 
@StackedCrooked That image is confusing as fuck.
 
2:10 AM
therefore the chromatic number is in NP
 
@nneonneo But if you have just the number, (without the actual solution), is it still poly to verify?
 
OK!! Bipartite graph -- you can split the nodes into two groups such that the edges only go from one group to another. Never between nodes in the same groups
@Mysticial: No. That would be the graph colouring problem, another NP problem.
 
Xeo
So you have to find those groups or what?
 
@Xeo: Or just say whether you can split the graph or not.
Simple example: a triangle graph is not bipartite
 
Xeo
Wait a sec
 
2:11 AM
@Xeo So see if it's even possible in the first place.
 
no matter how you divide up the three nodes, one of the edges will always go between two nodes in the same group
 
@Xeo Another way to think of this is: You color all the nodes in a graph either red or blue such that each node is not connected to any other node of the same color.
 
Xeo
k, I think I got it.
 
now, what happens if we get more colours to use?
 
So a graph without cycles is always bipartite?
 
Xeo
2:14 AM
Sometimes, if I have multiple somethings lying around together, I try to connect them without going connecting to a direct neighbour - would that also be something similar?
 
@StackedCrooked I think that's correct.
 
@nneonneo It becomes easier.
 
@StackedCrooked:a graph without cycles is a tree, and trees are bipartite because you can colour the odd levels red and the even levels blue
 
0
Q: vertical scroll bar in IE6

Sweta Priyai am facing problem on div tag with vertical scroll. when i minimize the window the scroll bar does not appear in a small size window. i am using Window Server 2003 sp2 and IE6 as client. Below is my div tag.. <div style="border: 1 none Black; vertical-align: top;overflow:auto; height:470px;...

Lol... IE6?!?!
 
@StackedCrooked: in fact, a graph with no odd cycles is bipartite
heh
 
2:14 AM
So the catch is. Determining whether or not a graph is bipartite is an "easy" task. Doable in polynomial time.
 
Ah, and a triangle has three edges, which is an odd number, so it's no biparite.
 
yep
 
@Doorknob how odd..if you minimize the window, there is no scroll bar? :p
 
immediately you can think of some easy ways to solve the problem quickly
 
But when you go to 3 colors or more, it becomes "hard". NP-complete. There is no known algorithm to do it polynomial time.
 
2:15 AM
haha
 
@Mysticial: neat, there's actually a site that shows the 3SAT reduction for graph 3-colorability: shannarasite.org/kb/kbse60.html
 
our customer use IE6, so i have no choice on this. — Sweta Priya 1 min ago
ahaha
 
@Doorknob: :'(
 
@nneonneo Traverse the graph and keep a list of all nodes you passed. If you meet a previously encountered node then the odd or evenness of the distance between those nodes determines bipartiteness?
 
by the way, with some of this background I think en.wikipedia.org/wiki/P_versus_NP_problem can be useful for understanding P and NP
@StackedCrooked: pretty close
you can skip the "distance" check by just assigning the nodes to groups as you see them
 
2:19 AM
With 'distance' I mean traveled distance.
 
right
but yeah, it's not a "hard" problem
 
just go start coloring like mad :D
 
yeah
 
@nneonneo Oh, lol.
 
but once you go to 3 colourability, it gets hard
because you can't rely on odd/even to help you
 
2:19 AM
Dammit.
 
and assigning randomly will result in back tracking between the two other colours
because, as it turns out, 3-colourability is NP-complete
(dunh dunh dunh!)
 
Xeo
Btw, how can you prove something to be NP-complete?
 
you reduce some other NP-complete problem to it
that shows the problem is NP-hard
then you just have to show it is in NP by demonstrating some way to verify a solution
 
@Xeo Suppose X is known to be NP-complete. And you show that you can solve X by solving Y, then you're proved that Y is NP-complete NP-hard.
 
well, almost
 
Xeo
2:22 AM
@nneonneo what if there was no other NP-complete problem? :)
 
you've proven that Y is NP-hard
 
@nneonneo Doesn't NP stand for "no problem"? Doesn't sound very hard to me ;)
 
@Xeo: there's a very famous theorem called Cook's theorem
which establishes the NP-completeness of a problem independently of any other NP-complete problem, by modelling a Turing machine
so, basically, they proved the first NP-complete problem
from there, they started reducing all these other problems
 
But how did they prove the first NP-complete problem without another NP-complete problem to reduce it to?
 
@StackedCrooked They just defined it that way.
 
2:24 AM
@Mysticial: not really...
it's a bit abstract, but basically they proved that any algorithm that solves an NP problem can be modelled using some instance of boolean satisifiability
 
@nneonneo It doesn't matter which one you use as the "master". Most of them reduce to each other no?
 
tell us tell us uncle nneonneo, why did the mad evil computer scientists create this evil NP completeness?
 
@Mysticial: nope, doesn't matter
@melak47: because they needed something to do
complexity theory was getting boring
(and now that all the easy research is done, and only the impossible P=NP problem remains, it's getting a bit boring again)
 
Xeo
Welp, atleast I now get what this whole P=NP deal is all about. Is what I think, anyways.
 
oh yeah, that
P=NP asks -- if it's so easy to verify a solution, is it easy to find the solution in the first place? And nobody knows.
right now we just kind of assume it's hard to find the solution for an NP-complete problem
so you say "NP-complete" and we just kind of go "aww, is there at least an approximation"?
by the way, NP-complete problems vary wildly in how easy they are to approximate
 
Xeo
2:28 AM
Mhm. And then, if any NP-complete problem happens to be solvable in polynomial time, shit hits the fan.
 
Oh yeah
 
@Xeo yes
 
big time
 
So, the 3-colourability is NP-complete because it's easy to verify, but NP-hard to solve.
 
well, it's suspected hard to solve
it's NP-complete because it's easy to verify, and other problems reduce to it
the difficulty of solving it doesn't actually factor into it
 
2:29 AM
right
 
by the way, there are some problems that are strongly suspected to be not NP-complete, but also not in P
of course this is impossible if P=NP, but the existence of such "middle-ground" problems suggests that P≠NP
for example, factoring integers is suspected to be not in P
but it's also not NP-complete, as far as anyone can tell
you see, there's a great deal of uncertainty about these things :(
 
Xeo
Well, I can't imagine how there couldn't be. :)
 
@nneonneo why is it not np-complete? is it not easy to check if a given set of factors make up a number?
 
Xeo
There's always the chance somebody stumbles upon a new solution that changes everything
 
@melak47: It's NP
as you said, it's easy to check if a given set of factors multiply to make a number
 
2:32 AM
Nobody has been able to reduce prime-factorization into any existing NP-complete problem.
 
oh.
 
Despite the fact that it is still a hard problem.
 
(any NP-complete problem into factorization)
 
blah blah....
 
lol
 
2:33 AM
actually, proving a number is prime was thought to be one of these "not-in-P" problems for a long time
until AKS came out with the "PRIMES is in P" paper that showed that you can prove primality in polytime
that paper gives a tiny glimmer of hope that factorization might be in P
but we're not there yet
 
@nneonneo Well... the rabin-miller algorithm has arbitrarily high certainty. And if the Riemann Hypothesis held, then Rabin-Miller automatically becomes deterministic with enough iterations.
 
but but, if factorization is in P, doesn't that break encryption and shit? D:
 
Xeo
I wonder if we even want to find P=NP to be true.
 
So it was kind of a barrier that was ready to fall.
 
@Mysticial: true, but AKS shows that without requiring Riemann
though since everyone basically assumes Riemann is true (*), I guess it's a moot point
 
2:35 AM
If we find the answer as to whether P=NP. What will the implications be?
 
@StackedCrooked that computers are even more awesome than before :D
 
@StackedCrooked You get the largest e-penis in the world for about 2 weeks.
 
@StackedCrooked: any solution to that problem probably involves new math
i.e. entirely new approaches to problems
 
@melak47 Yes it does.
 
2:36 AM
so even if we find P≠NP, the field of math and theoretical CS gets a big step up
of course, if we find that P=NP then everything changes
(gradually)
P=NP is an interesting case
the proof might not be constructive
 
@nneonneo ....if P=NP, would that mean there are no problems that aren't in P? or would we still have another class of hard problems :/
 
Xeo
I wonder if all this isn't moot anyways thanks to quantum computing. :)
 
in which case, it says that there is a polytime solution to an NP-complete problem, but doesn't say what the algorithm is
 
@Xeo I was thinking the same :)
 
@Xeo: BQP is a thing
 
2:38 AM
@Xeo Quantum computing will solve factorization. But it is not believed to solve NP-complete problems.
 
Will NP problems be solvable with quantum computing?
Oh.
 
BQP: the class of problems solvable by a bounded-error quantum computer in P time
 
@nneonneo Right.
 
It is suspected that not all NP problems can be solved by BQP
in which case quantum computers don't magically give us the ability to solve NP-complete problems in polytime
quantum computing, by the way, is mind bending
you do crazy stuff like compute quantum fourier transforms (QFTs) to find integer roots
 
Shor's algorithm for factorization is pretty crazy.
 
2:40 AM
@melak47: if P=NP, all NP problems are in P
 
Quantum fourier transform to extract the modular repetition frequency.
 
there is another class of harder problems
 
@nneonneo but, there are more problems, right?
 
yes
PSPACE, EXPSPACE, ALL
 
Once you have that frequency, then you do continued fractions to construct it...
 
2:41 AM
and dozens of complexity classes in between
 
some day they are going to look back at this as the dark ages of cs... they couldn't even figure out if P=NP!
 
@Mysticial: isn't it repeated squaring? the way they taught it in QC was that the algorithm's postprocessing amounted to repeatedly doubling a very tiny angle
 
@nneonneo It's a bit different than what I read.
 
effectively, the solution shows up as an absolutely minute bump in one of the fourier coefficients, so you basically square the whole thing repeatedly (which has the same effect as doubling the phase angle) until the thing aligns with an axis you can easily read off
it's bonkers
 
IIRC, you evaluate the power modulus to every power simutaneously. And perform a quantum FFT on it. Because modulus is periodic, it will show up as a spike in the frequency domain.
 
2:44 AM
ja
 
You measure that spike to get the frequency. And use continued fractions to construct it back into an integer ratio.
And that is essentially the factor.
 
bahnhof is all I'm getting here :p
 
hm. my notes from QC are somewhere...
 
Just checking: P means time required is upper bound by input_size^a_constant. So if a problem requires input_size^input_size time then it's not P, and thus NP. (Unless it's one of those middle cases?)
 
An Introduction to Quantum Computing by Kaye, LaFlamme and Mosca
@StackedCrooked: something like O(n^n) is probably NP-complete.
probably.
remember, any practical problem you are likely to run into is NP-complete
except those crazy PSPACE-complete things like generalized Go
 
2:46 AM
The go board game?
 
yeah
generalized Go is played on an arbitrarily big surface
the question "who wins" is PSPACE-complete
 
what problem class would you say does writing a standard compliant C++ compiler fall in? :v:
 
@melak47: well, a C++ compiler can calculate basically anything by virtue of template metaprogramming
writing the compiler is a solved problem
 
and TMP is turing complete
 
tmp?
 
2:49 AM
template meta-programming
 
template metaprogramming :p
 
oh yeah
 
template masturbation meta programming.
 
durr
yeah, TMP is turing complete
there's a whole interesting discussion in there
 
Xeo
constexpr is turing-complete too~
 
2:49 AM
Your mom is turing complete.
 
too obvious :p
 
Xeo
I wonder if the CPP is turing-complete too.
Which would mean we got 4 touring-complete languages in 1. Who can beat that deal?
 
TMP can do selection and recursion. I think this fulfills the Turing completeness requirements?
A file can include itself, so you can have iteration. And you also have selection with #if and #ifdef.
 
a file can include itself? o.O
 
Xeo
BOOST_PP_ITERATE <3
 
2:52 AM
30
A: Is the C99 preprocessor Turing complete?

PaulWell macros don't directly expand recursively, but there are ways we can work around this. The easiest way of doing recursion in the preprocessor is to use a deferred expression. A deferred expression is an expression that requires more scans to fully expand: #define EMPTY() #define DEFER(id) i...

basically, the answer is "probably".
yeah, C++ is insane
@melak47: yeah, files can include themselves. popularly abused by IOCCC entrants
there are some really clever IOCCC entries that cause cpp to take up ungodly amounts of time or space through recursive includes
 
Xeo
@nneonneo Well, Boost.Preprocessor is awesome after all.
 
yeah, that too
 
Xeo
And the facilities there suggest that it is indeed turing complete
 
Turing complete in a very messy, ass-backwards kind of way.
 
Xeo
room topic changed to Lounge<C++>: Try and beat our 4-in-1 turing-complete languages deal. [c++] [c++11] [c++-faq] [no-helpdesk]
 
2:55 AM
By turing-complete nonetheless.
 
I think it's not Turing complete. The expansion must stop at one point.
Unless you use __COUNTER__ perhaps.
 
Xeo
@StackedCrooked That's just like we have finite memory.
In practice, nothing is turing-complete.
But in theory, all 4 sublanguages of C++ are.
 
4?
There's only 3: template metawankery, preprocessor, and then the language itself.
 
Xeo
CPP, Core, constexpr, TMP
 
Oh.
 
2:58 AM
Core?
 
Xeo
@melak47 Well, just C++ itself
The "runtime" part, so to speak
 
@Xeo oh - CPP == pre processor
 
Xeo
Yes
 
Xeo
#if N < 10
N
 
2:59 AM
I'm printing N.
 
Xeo
@StackedCrooked Btw, clicking "edit" should give you the command line from the link
 
@Xeo Yeah.
 
Ohai. Trivia: what does the following print (no cheating!)
#include <complex>
#include <iostream>

// imaginary numbers
std::complex<long double> operator "" _i(long double d) // cooked form
{
    return std::complex<long double>(0, d);
}

int main(int argc, const char *argv[])
{
    auto val = 2._i; // val = complex<long double>(0, 2)
    val *= -val;
    std::cout << val << '\n';
    val *= -val;
    std::cout << val << '\n';
}
 
Xeo
@sehe If you did that in a loop, you'd get a kind of spiral, right?
Welp, or not
 
Ah welp. I think we both had the same thinko: val *= -val :)
Anyways, look what I found in t.co/dmjeCZJkDt (it's on slide #28)
I can no longer maintain I'm never present at technical conferences
 
3:10 AM
@sehe: 4, then -16?
 
@nneonneo You get the mixer
 
sorry, my american culture is not good
what is mixer ?
 
I'm not american :)
 
that...is an eggbeater.
 
It's funny for "you get a lousy prize"
 
3:13 AM
aha
 
Sleep well!
 
..?
 
4:13 am here
 
night
 
Xeo
Same
G'night :)
 
3:14 AM
night
 
Xeo
And thanks @nneonneo @Mysticial for enlightening me. ;)
 
Can you explain why it's (4,-0) before you go? :|
 
4, -0?
 
@Xeo night
 
Xeo
@Rapptz think of the i part as rotation and scaling
 
3:14 AM
wh?
oh, what it outputs
...it's like they don't teach imaginary numbers anymore?
 
Xeo
the sign determines whether you rotate CCW (+) or CW (-) on the imaginary plane
 
@nneonneo eh?
 
Xeo
the number determines the scale applied.
 
@nneonneo ??
 
what was this about a spiral?
ok, why is val *= -val confusing?
 
3:17 AM
It isn't?
 
ok
...
 
my guess was 4, -16
I've never used std::complex
 
Xeo
(0, 2) * (-0,-2) -> the point (0, 2) is on the Y axis, if you will, and rotates CW (negative imaginary part) -> (2, -0) -> the 2 scales by 2 -> (4, -0)
 
wait, the output is 4, -0? that would surprise me
 
@nneonneo Yes
 
3:18 AM
...
 
4, -0 and -16, 0
 
Xeo
@Rapptz -16
 
my bad
Oh I forgot to apply - to the zero.
 
oh haha
I see
 
Xeo
and after (4, -0), you multiply again, this time by (-4, 0), which means no rotation and times -4 for scaling.
 
3:19 AM
I didn't quite understand how std::complex would be output
so yeah, (4,-0) is just 4-0j
and (-16,0) is -16+0j
in other words, 4 and -16
 
yeah
 
Xeo
Y U j :P
 
hey, it's the standard in engineering
and I'm a Python programmer, where it's typically j
>>> 4+2j
(4+2j)

and all that
 
Xeo
And once you are on negative X, -val will give a positive scaling, meaning you just scale farther into negative X.
 
I just forgot to distribute the negative to the zero
 
3:21 AM
@Rapptz: to be perfectly fair, I don't think you normally have to do that in math
predicting when zeros will sprout negatives in C++ is not that much fun, I think
@Xeo: so how do you interpret (1+1j) * (1+1j)?
 
(i+1)^2 = 2i?
 
mhm
actually isn't that hard to see when you view it as a scaling+rotation
 
Xeo
I just find it easier to visualize arithmetic with complex numbers that way
I just view them as some kind of bastardized child of points and 2D vectors.
 
hm
y'know, I still don't understand quaternions
 
Xeo
Me neither. They're dicks. :<
 
3:29 AM
A range is responsible for keeping track of its current position in the range, right?
Much like an Enumerator from C# ?
@nneonneo Quaternions are the fucking devil and should die in a horrific fire.
 
Xeo
What kind of range are you talking about?
 
All the ranges.
 
@ThePhD: how else do you do free-space rotation transforms without horrific singularities?
 
@nneonneo Changing the reference vector, yo.
 
Xeo
@ThePhD In current C++, you get the iterators from the ranges, and go from there. The range does nothing.
 
3:32 AM
@ThePhD and how do you rotate the reference vector?
 
@nneonneo You select a second reference vector and use that when you're not swirling about the first one.
 
then a third for z...so you are just constantly rotating the reference frame around?
 
Yep.
:D
 
ah. I see that would be easier.
 
Of course. :D
 
3:38 AM
so basically you're what, storing a rotation matrix?
 
A vector.
Or maybe I'm not?!
Who knoooows?!
 
@ThePhD lol
 
Xeo
Alright, time to really get to sleep.
 
And do more sleep-talking?
 
@Xeo: night
 
Xeo
3:48 AM
It's close to 5am here now, and I only stayed awake till now because of the turing-completeness stuff
G'night everyone
 
night, for real :p
 
4:03 AM
0
Q: The differences between Java and C++ in efficiency

iantangI have learnt the entry knowledge of both Java and C++, the auto release memory function from Java is amazing and the structure of class of Java is more decent (it is only my own opinion, please ignore it if you disagree with it). I understand why Java is said to be more programmer friendly than ...

 
4:55 AM
So, anyone here running for mod?
 
@GamesBrainiac Flexo is
 
@Pubby Who is flexo?
 
Since Mooing Duck is not running, I guess I really am not voting for anyone.
 
I thought about it, but I know I wouldn't make it since I would ban all the @$$-hats that flame new SO users with "uhhh google dude" comments. So basically, SO would have only 3-5 remaining users.
 

« first day (875 days earlier)      last day (4082 days later) »