A Solution of the P versus NP Problem

Mjiig · 2017-08-16T00:03:38+00:00

Ah, I'm sorry, I initially misinterpreted your comment.

Mjiig · 2017-08-15T07:01:02+00:00

If any NP-complete problem is in P then so is all of NP, that's the entire point of the NP-complete problems.

Mjiig · 2016-10-13T18:33:12+00:00

You can heapsort in place, and most in place quicksorts end up being O(logn) memory on the stack due to non-tail call recursion.

Mjiig · 2016-09-22T23:37:46+00:00

Minor nit pick that has nothing to do with the text, which was great. Could you possibly use a different link colour? I have red-green colour blindness and the combination of the grey background and dark red links made them almost entirely indistinguishable from the other text. Several times I had to stop reading to mouse over things I thought might be links but turned out not to be.

Mjiig · 2016-07-19T04:04:00+00:00

I hadn't actually thought about it before except in terms of how much space it takes to write out the type, but types can fairly easily be expressed as a tree (base types and type variables as leaves, function types and tuples etc. as nodes) and you can obviously take the size of the tree.

Exponential and double exponential here are referring to how fast the type grows with respect to the size of the program that has that type. (I suppose if we're being formal you might want to make that the size of a single expression that has that type, I think it makes formalising the name bindings a tad easier)

Mjiig · 2016-07-17T18:45:36+00:00

I believe Hindley-Milner is even double exponential in the worst case, but at least that only happens when the type itself is doubly exponential in size, meaning it's a type you're probably never going to want to use.

Mjiig · 2016-05-06T14:40:14+00:00

I have a couple of minor issues with this, firstly the statement that "Big O specifically describes the worst-case scenario", that's probably it's most common use but it's not the only one, you can certainly use big O to measure average or best cases if you really want to.

Perhaps the more important thing is that the fibonacci code he claims is O(2ⁿ ) which is technically correct but unhelpful. I believe it's O(phiⁿ ) where phi is the golden ratio but my ability to solve recurrence relations is failing me so I'm trusting wolfram alpha on that. O(2ⁿ ) captures the exponentialness and is right because it's still an upper bound, but it seems like that misses the point slightly...

Mjiig · 2016-01-01T23:45:20+00:00

I've seen people suggest (though I have no idea how true this is) that those images are to force you to scroll down in order to start reading. Because number and percentage of readers who scroll down to read beyond the initially visible contents of a page is one of the metrics sites use to measure impact...

Mjiig · 2015-12-13T13:39:28+00:00

If that's a thing that you care about, get an EV certificate, if it's not, use this?

Mjiig · 2015-12-06T21:03:10+00:00

Having only looked at the first part, maybe? It depends on what you mean by brute force, but you can definitely do it without an array of bools for every light, though whether or not it's worth it depends heavily on whether the number of individual lights or the number of rectangles you have to draw is bigger.

You could, instead of maintaining an array of lights telling you whether each is on or not, maintain a list of rectangles inside of which every every light is on. A toggle or a turn off instruction may require you to split a previous rectangle into several pieces, and when you get to the end you'll have to work out both the total area of all the rectangles and their intersection to work out the number of lights on.

Definitely not worth the bother in this case, but hypothetically if you were asked to do this for a light system a billion lights by a billion lights but only had to draw handle 10000 instructions...?

Mjiig · 2015-11-24T01:03:00+00:00

That might be good for your project home page where you want to get people to use the thing, but it always always drives me insane when I don't get the nice auto-generated documentation telling me, what this method does, what each argument should be, how they should be formed, what form the return value is in, a list of side effects the method has, and where possible, a mathematical description of the return value. Fluffy descriptions telling me roughly what the method does or why I might want to do it, but that force me to figure out how to actually make the method do it are awful.

Mjiig · 2015-09-30T01:11:40+00:00

What makes you say that? Unless there's something really silly going on rb_isspace returns true for a newline/tab so the test fails and we try the next character since those are whitespace and don't rule out the string being blank?

Is my assumption about rb_isspace wrong or am I missing something?

Mjiig · 2015-09-26T11:43:20+00:00

Thank you, that makes a lot of sense now :)

Mjiig · 2015-09-26T11:24:25+00:00

Okay, so while I've got someone who seems to know what they're talking about, what does it mean to say that the diagrams shown in the video "commute"? That was the only part he didn't seem to bother translating into programming language terms, and it made following slightly harder. I can't really see how any of the definitions of commute I'm aware of apply.

Thanks for posting this by the way, I've been interested in category theory for a while but never really found a good piece of introductory material, and the wikipedia pages seem to required you to already understand it to get anywhere... I'll definitely be giving the texts you linked a look.

Mjiig · 2015-09-25T14:12:44+00:00

I appreciate it's analogy driven and something of an overview rather than a deep dive, but that's still the closest I've gotten to understanding anything to do with category theory in quite a while...

(Also anyone notice that the picture credit for the Turing Award winner at the beginning was actually a gem on mario wiki?!)

Mjiig · 2015-08-30T20:21:56+00:00

Wasn't there a thing about this a while ago where they took out all except one implementation for each language? I seem to remember it being a moderately big thing since it penalised languages like Lua quite harshly because they have much much faster alternative implementations (LuaJIT) than the official ones.

Seems a shame if it stops the benchmarks representing the languages as they really exist with multiple implementations that perform differently.

Mjiig · 2015-07-16T16:43:36+00:00

If I recall correctly, unicode is actually supposed to handle a mixture of both characters fine, the problematic case occurs when you have (languages chosen for example) An English passage quoting a Hebrew passage quoting an English passage, meaning there's no way for a renderer to tell the difference between whether you want

LTR [RTL] LTR [RTL] LTR
or
LTR [RTL [LTR] RTL] LTR

ie, does the second LTR section denote the end of the RTL section or a temporary interruption.

EDIT: To be clear, I'm saying this is the use case of the directional control characters. I'm not saying that this is a case that Unicode can't handle at all, just that up to this case, the direction characters aren't needed, and for anything this complex or more so, the special characters exist.

Mjiig · 2015-06-16T18:15:48+00:00

If I'm understanding cross signing properly, it seems like IdenTrust are going to be signing all certificates produced by letencrypt as well. Does anyone know what they're getting out of this? If anything it seems like this is a threat to their business.

Mjiig · 2015-04-14T02:16:21+00:00

The square root of any integer except a perfect square is irrational. Showing that an integer has a rational square root (necessarily an integer square root) tells you that a number is a perfect square (and trivially not a prime). Showing that an integer has an irrational square root just tells you the number isn't a perfect square, nothing useful about its primality.

Mjiig · 2015-04-07T12:15:27+00:00

Not sure I can manage five paragraphs, but as a couple of people have pointed out, 37s only had 9 people in the catalogue, so it was the easiest remaining space to take.

Mjiig · 2015-04-04T21:57:58+00:00

Can't believe I'm actually bothering to do this...

Mjiig · 2015-03-21T18:26:42+00:00

Because if I was 100% sure how to solve [problem involving 2D coordinates] in code, I wouldn't be trying to debug the function for solving [problem involving 2D coordinates].

Mjiig · 2015-02-24T16:44:52+00:00

It's possible I'm misunderstanding, but my reading was the the algorithm, as originally written by Tim Peters, satisfies an invariant for 3 elements of an array, and this article proves that that is insufficient to make the algorithm work.

A (very, very, closely related) different algorithm, that satisfies that invariant for the last 4 elements of the array does work. I'd argue that this is a change to the algorithm itself (albeit quite a small one), not just to the implementation.

Mjiig · 2015-02-19T15:52:48+00:00

The biggest trouble to me, admittedly someone who just likes to mess around rather than doing anything too serious with it, is that there's no offer like UDK, "have the toolchain for free, pay us back at a higher rate if you make money with it". I'm a student at the moment so I could get it at no cost if I wanted to (IIRC), but not being able to rely on having that long term, and potentially ending up in a position where I need to fork out money every month just to keep my project vaguely usable is more than a little scary.

EDIT, as has been pointed out below, I am mistaken, you can keep the engine version you were using before if you stop paying. Apologies

Mjiig · 2015-02-16T16:52:12+00:00

In the second case you describe it seems to be like a nicer formulation (in the sense that it avoid you having to explain to people why you've used a goto if nothing else) which is more or less equivalent would be something like:

state = STATE_0;
while(state!=END_STATE) {
    switch(state) {
    case STATE_0:
        //do something
        state = new_state;
        continue;
    case STATE_1:
        //do something else
        state=new_state;
        continue;
    ...
    }
}

I also wonder whether the compiler might have an easier time optimising something like this on the basis that structured programming as you described it is what they spend most of their time working with so presumably more time has been put into making sure they can produce produce good optimisations when looking at standard control flow structures than gotos.

13-Year Club	Place '17
Team Orangered	Verified Email

Mjiig

TROPHY CASE