| --- Log opened Mon Mar 31 00:00:27 2014 |
| 00:09 | <@celticminstrel> | I have discovered that xmllint is very user-unfriendly. |
| 00:11 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 00:24 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 00:24 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 00:28 | < [R]> | But XML and user-friendliness go hand in hand, just like white wedding dresses and being a MS and/or Sony fanboy. |
| 00:29 | <&McMartin> | I like it when things like game data files are XML thingies instead of binary blobs. It makes modding easier. >_> |
| 00:29 | <&McMartin> | (And there are places it's preferable to JSON in that use case) |
| 00:30 | <&McMartin> | (Though JSON is often good enough!) |
| 00:30 | < [R]> | JSON goes into a nicely duck-typed data structure though |
| 00:30 | < [R]> | XML needs to be accessed through OOP :/ |
| 00:31 | <@celticminstrel> | What I really meant was that it seems to be impossible for me to get it to do what I want. |
| 00:32 | <&McMartin> | R: Yeah, the places where XML is preferable is places where for whatever reason you do not *want* duck typing |
| 00:32 | <&McMartin> | Say because you've got some kind of external invariants you need to enforce, so tagging makes that easier to check. |
| 00:33 | | * McMartin wonders how much of the static vs. dynamic typing argument can just be pasted into JSON vs. XML |
| 00:33 | < [R]> | I meant more for using a scripting language to mutate the data externally :/ |
| 00:34 | < [R]> | Only done it in PHP and JS, Python would probably work nicely too. |
| 00:39 | <&McMartin> | Python's actually pretty great at both. |
| 00:39 | < [R]> | Python has xml_parse() and xml_stringify()? |
| 00:39 | <&McMartin> | XPath is pretty great as a selector mechanism. |
| 00:39 | <&McMartin> | Python has multiple modules for dealing with XML |
| 00:40 | <&McMartin> | I've always just used minidom. |
| 00:40 | < [R]> | Eww, missing the point |
| 00:40 | <&McMartin> | And I've generally been able to rip out what I want with list comprehensions. |
| 00:40 | <&McMartin> | If you want to get a data structure out of an xml file, yes, you call one function and feed it a string. |
| 00:40 | < [R]> | JSON libs are almost always 2 or 3 functions: unparse, parse and (sometimes) getError |
| 00:41 | <&McMartin> | Yeah, that's not always a feature =P |
| 00:41 | <&McMartin> | That's only a feature if you're trying to use it for *pickling*, and you shouldn't =P |
| 00:41 | < [R]> | No matter what, you're going to have to do type-checking |
| 00:42 | < [R]> | Err validation |
| 00:42 | <&McMartin> | Well, absent a schema, yes |
| 00:42 | <&McMartin> | I suppose one could phrase it "if you're going to be tagging all the fields *anyway*..." |
| 00:43 | <&McMartin> | Monocle's resource format was basically a tossup, but JSON won because too many things weren't tagged meaningfully. |
| 00:43 | < [R]> | ... and that's how it should be. |
| 00:44 | < [R]> | XML's tollerable if you need to be using attributes. Mostly because there's nothing else that works. |
| 00:44 | <&McMartin> | Right |
| 00:44 | <&McMartin> | Monocle's resource format is for things like sprites and such, where attributes are arguably sensible |
| 00:44 | <&McMartin> | But it wasn't worth the parsing effort, especially since Monocle is trying to minimize external dependencies. |
| 00:45 | <&McMartin> | (I rolled my own JSON parser because it took an afternoon) |
| 00:46 | <&McMartin> | It turns out specifying sprites is one of those places where attribute vs. child really is a tossup =P |
| 00:46 | <&McMartin> | And yes, the various lossless "more textual" XML transformers can all die in fires. |
| 00:46 | <&McMartin> | YaML: All the disadvantages of XML, but harder to check by-eye that it is correct! |
| 00:49 | < [R]> | YAML is a sin |
| 00:49 | < [R]> | Just like pep8 is. |
| 00:49 | <@celticminstrel> | Whee. |
| 00:49 | < [R]> | :p |
| 00:49 | <@celticminstrel> | Converting DITLs to xml! |
| 00:50 | <@celticminstrel> | I should probably automate it, but that would require accessing resources. |
| 00:58 | | You're now known as TheWatcher[T-2] |
| 01:00 | | You're now known as TheWatcher[zZzZ] |
| 01:00 | | Reiv [NSwebIRC@Nightstar-q8avec.kinect.net.nz] has quit [Ping timeout: 121 seconds] |
| 01:13 | | Reiv [NSwebIRC@Nightstar-q8avec.kinect.net.nz] has joined #code |
| 01:13 | | mode/#code [+o Reiv] by ChanServ |
| --- Log closed Mon Mar 31 01:31:39 2014 |
| --- Log opened Mon Mar 31 01:37:27 2014 |
| 01:37 | | TheWatcher[zZzZ] [chris@Nightstar-ksqup0.co.uk] has joined #code |
| 01:37 | | Irssi: #code: Total of 36 nicks [17 ops, 0 halfops, 0 voices, 19 normal] |
| 01:37 | | mode/#code [+o TheWatcher[zZzZ]] by ChanServ |
| 01:38 | | Irssi: Join to #code was synced in 38 secs |
| 01:45 | <@celticminstrel> | The transformation seems to work, since inspect element shows the <br> elements in the HTML, but it's not being rendered as a line break. |
| 01:47 | < [R]> | ... XSLT is removing the self-closing property? |
| 01:47 | < [R]> | The fuck |
| 01:47 | < [R]> | That's horrible. |
| 01:47 | <@celticminstrel> | Oh, I found it, my CSS stylesheet had a * rule that broke it. |
| 01:47 | < [R]> | How is it not bitching about the unclsoed br? |
| 01:48 | <@celticminstrel> | I have no idea what you're talking about... |
| 01:48 | <@celticminstrel> | Oh, when I said <br> elements were shown in Inspect Element, they were actually <br></br>. |
| 01:48 | <@celticminstrel> | The XSLT had <br/>. |
| 01:49 | < [R]> | Ah |
| 01:49 | < [R]> | Yeah, the /> at the end instead of just > means the tag is self-closing. |
| 01:49 | <@celticminstrel> | I'm aware! |
| 01:49 | < [R]> | One of the things they "fixed" with XHTML |
| 01:51 | | himi [fow035@Nightstar-q9amk4.ffp.csiro.au] has joined #code |
| 01:51 | | mode/#code [+o himi] by ChanServ |
| 02:23 | <@celticminstrel> | Hm, I wonder if there's a way for the XSL to strip tabs but not spaces... |
| 02:23 | <@celticminstrel> | Tabs and newlines, actually. |
| 02:24 | | VirusJTG [VirusJTG@Nightstar-6i5vf7.sta.comporium.net] has quit [[NS] Quit: Program Shutting down] |
| 02:31 | <@celticminstrel> | Oh hey, it worked. (Discovered the translate() function.) |
| 03:09 | | Orthia [orthianz@Nightstar-3tp.juj.184.203.IP] has joined #code |
| 03:09 | | mode/#code [+o Orthia] by ChanServ |
| 03:09 | | Reiv [NSwebIRC@Nightstar-q8avec.kinect.net.nz] has quit [Ping timeout: 121 seconds] |
| 03:27 | | Ghozer [theeaznon@Nightstar-isnf1r.sfldmi.sbcglobal.net] has joined #code |
| 03:27 | <@celticminstrel> | I suspect XCode 4 never closes any files. |
| 03:28 | <@celticminstrel> | Because when I quit, I see it cycling through a lot of files I'd previously had open. |
| 03:28 | <@celticminstrel> | As if it's closing them all. |
| 03:29 | <@celticminstrel> | Maybe that's not the correct interpretation, but it sort of makes sense to me. |
| 03:29 | | HotShot [theeaznon@Nightstar-ohh9ir.sfldmi.sbcglobal.net] has quit [Ping timeout: 121 seconds] |
| 03:39 | | Ghozer is now known as HotShot |
| 03:50 | | Reiv [NSwebIRC@Nightstar-q8avec.kinect.net.nz] has joined #code |
| 03:50 | | mode/#code [+o Reiv] by ChanServ |
| 04:04 | | Kindamoody[zZz] is now known as Kindamoody |
| 04:16 | | HotShot [theeaznon@Nightstar-isnf1r.sfldmi.sbcglobal.net] has quit [Connection closed] |
| 04:52 | | Derakon is now known as Derakon[AFK] |
| 05:35 | | JackKnife [Z@Nightstar-484uip.cust.comxnet.dk] has joined #code |
| 05:35 | | mode/#code [+o JackKnife] by ChanServ |
| 05:50 | | RchrdB [RichardB@Nightstar-c6u.vd5.170.83.IP] has quit [[NS] Quit: Gone.] |
| 05:53 | | RchrdB [RichardB@Nightstar-c6u.vd5.170.83.IP] has joined #code |
| 06:15 | | ErikMesoy|sleep is now known as ErikMesoy |
| 07:01 | | celticminstrel [celticminst@Nightstar-mhtogh.dsl.bell.ca] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| 07:15 | | Erik [8f610223@Nightstar-qtq4f2.mibbit.com] has joined #code |
| 07:40 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Connection closed] |
| 08:09 | | Kindamoody is now known as Kindamoody|afk |
| 08:23 | | himi [fow035@Nightstar-q9amk4.ffp.csiro.au] has quit [Ping timeout: 121 seconds] |
| 08:31 | | thalass [thalass@Nightstar-90oetb.bigpond.net.au] has joined #code |
| 08:31 | | mode/#code [+o thalass] by ChanServ |
| 08:38 | | Kindamoody|afk is now known as Kindamoody |
| 09:02 | | You're now known as TheWatcher |
| 09:08 | | macdjord is now known as macdjord|slep |
| 10:12 | | mode/#code [+o RchrdB] by ChanServ |
| 10:38 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has joined #code |
| 10:38 | | mode/#code [+o himi] by ChanServ |
| 11:09 | | Kindamoody is now known as Kindamoody|out |
| 11:17 | | gnolam [lenin@Nightstar-d469ie.cust.bredbandsbolaget.se] has quit [[NS] Quit: Gone] |
| 11:54 | | gnolam [lenin@Nightstar-3pr.n94.131.88.IP] has joined #code |
| 11:54 | | mode/#code [+o gnolam] by ChanServ |
| 12:03 | | Reiv [NSwebIRC@Nightstar-q8avec.kinect.net.nz] has quit [Ping timeout: 121 seconds] |
| 12:11 | | VirusJTG [VirusJTG@Nightstar-6i5vf7.sta.comporium.net] has joined #code |
| 12:22 | | Syka [the@Nightstar-qam.i8a.156.120.IP] has joined #code |
| 12:23 | | Syka is now known as NSGuest49540 |
| 12:30 | < Erik> | Maaaan. Today my coworker (the one who gets high on objects) is ripping on backward compatibility. |
| 12:31 | < Erik> | He thinks that backward compatibility is fundamentally a deluded idea: if you want the new thing to work like the old thing, why are you making a new thing? |
| 12:31 | < Erik> | you should either be updating the old thing, or making an incompatible new thing. |
| 12:33 | < Erik> | This came up where he was hating on Microsoft for (strange functionality) and I suggested that maybe it's a bit cheap to hate "Microsoft" as an abstract evil when the strange functionality might be due to design under constraints of 1) support old thing for 30 years and b) be backwards-compatible with old thing. |
| 12:34 | <@gnolam> | Ah, zealots. |
| 12:34 | < Erik> | (Strange functionality was something to do with network paths that I didn't really understand, so I'm willing to cede that point.) |
| 12:35 | <&McMartin> | Is this guy an Apple fan by any chance |
| 12:36 | <&McMartin> | Since they take a bit of a Logan's Run approach to backcompat |
| 12:43 | < Erik> | McMartin: yes |
| 12:45 | | * gnolam checks to see if the Apple Store uses carousels. |
| 12:46 | | thalass [thalass@Nightstar-90oetb.bigpond.net.au] has quit [Ping timeout: 121 seconds] |
| 13:00 | <@Tarinaky> | http://thecodelesscode.com/case/138 |
| 13:11 | < NSGuest49540> | gnolam: yes |
| 13:12 | < NSGuest49540> | gnolam: apple front page does, plus the top of apple store |
| 13:17 | | NSGuest49540 [the@Nightstar-qam.i8a.156.120.IP] has quit [[NS] Quit: lol3g] |
| 13:18 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 13:31 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has joined #code |
| 13:32 | | mode/#code [+o himi] by ChanServ |
| 13:41 | <@Tarinaky> | Erik: Point out it's a false dilemma? Suggest an example of a Word Processor that only supports a non-standard ASCII-derived charset. To make it support UTF8, the spell-checker unit of code needs replacing. Should they also throw away their english language dictionaries or would backwards compatibility with old dictionary formats be acceptable? |
| 13:43 | <@Tarinaky> | What about if the maker of this Word Processor doesn't want to update it to support UTF8, so a competitor writes a new word-processor with the end-goal of all the same features, but in Russian. Should it not be back-compatible with the other document format? |
| 13:50 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 13:55 | | gnolam_ [lenin@Nightstar-3pr.n94.131.88.IP] has joined #code |
| 13:57 | | gnolam [lenin@Nightstar-3pr.n94.131.88.IP] has quit [Ping timeout: 121 seconds] |
| 14:02 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has joined #code |
| 14:02 | | mode/#code [+o himi] by ChanServ |
| 14:27 | <@Azash> | Backwards compatibility is the kind of subject where neither kind of extremism works |
| 14:27 | <@Azash> | It's useful to a certain degree but you still need to recognize when it's actually degrading your software |
| 14:29 | < Shiz> | like how win64 still has 16-bit era APIs |
| 14:29 | < Shiz> | when they don't even support 16-bit applications anymore |
| 14:47 | | gnolam_ is now known as gnolam |
| 14:47 | | mode/#code [+o gnolam] by ChanServ |
| 15:08 | | gnolam_ [lenin@Nightstar-3pr.n94.131.88.IP] has joined #code |
| 15:10 | | gnolam [lenin@Nightstar-3pr.n94.131.88.IP] has quit [Ping timeout: 121 seconds] |
| 15:13 | | gnolam [lenin@Nightstar-3pr.n94.131.88.IP] has joined #code |
| 15:13 | | mode/#code [+o gnolam] by ChanServ |
| 15:15 | | gnolam_ [lenin@Nightstar-3pr.n94.131.88.IP] has quit [Ping timeout: 121 seconds] |
| 15:25 | | gnolam [lenin@Nightstar-3pr.n94.131.88.IP] has quit [[NS] Quit: Gone] |
| 15:43 | | ErikMesoy [Erik@Nightstar-6v0.mal.203.80.IP] has quit [Ping timeout: 121 seconds] |
| 15:43 | | ErikMesoy [Erik@Nightstar-6v0.mal.203.80.IP] has joined #code |
| 15:44 | | mode/#code [+o ErikMesoy] by ChanServ |
| 16:52 | | Orthia [orthianz@Nightstar-3tp.juj.184.203.IP] has quit [Ping timeout: 121 seconds] |
| 18:13 | | HotShot [theeaznon@Nightstar-lm0lil.sfldmi.sbcglobal.net] has joined #code |
| 19:28 | | Kindamoody|out is now known as Kindamoody |
| 19:50 | | Kindamoody is now known as Kindamoody[zZz] |
| 20:16 | | Orthia [orthianz@Nightstar-3tp.juj.184.203.IP] has joined #code |
| 20:16 | | mode/#code [+o Orthia] by ChanServ |
| 20:42 | | * ErikMesoy attempts to set up InspIRCd and finds himself mostly doing this by fixing one error at a time when trying to run it. :P |
| 20:43 | <@ErikMesoy> | No manual. Setup guide says "see conf files". Conf files are a dozen .conf.example files with most of their stuff commented out. |
| 20:44 | < AnnoDomini> | Why are you trying to set up your own IRC server? |
| 20:44 | <@ErikMesoy> | So that I can test a dicebot on it without getting g-lined for repeatedly reconnecting after tinkering with the code, as happened when I tried in #test around here. |
| 20:45 | | thalass [thalass@Nightstar-90oetb.bigpond.net.au] has joined #code |
| 20:45 | | mode/#code [+o thalass] by ChanServ |
| 20:49 | <@ErikMesoy> | FARF. The *main* conf file is 900 lines and after fixing a bunch of the early stuff like linking rules.txt.example, I run into a so-called "RTFM line" partway through which is there to ensure I have read all of the config file options. |
| 20:54 | <@ErikMesoy> | Welp. Skipped a bunch of those lines, got it to run, no idea how to make the bot connect there now. |
| 20:55 | <@ErikMesoy> | Anyone want to suggest an IRC server setup thingy that works out of the box with minimal features? (the only feature I want is "knowing how to connect to it") |
| 20:56 | | thalass [thalass@Nightstar-90oetb.bigpond.net.au] has quit [Ping timeout: 121 seconds] |
| 20:59 | <@ErikMesoy> | inspircd spat out an address to cmd, telling bot to go there failed |
| 21:20 | <@Azash> | Shiz: Yeah, exactly |
| 21:22 | | celticminstrel [celticminst@Nightstar-mhtogh.dsl.bell.ca] has joined #code |
| 21:22 | | mode/#code [+o celticminstrel] by ChanServ |
| 21:23 | | Reiv [NSwebIRC@Nightstar-q8avec.kinect.net.nz] has joined #code |
| 21:23 | | mode/#code [+o Reiv] by ChanServ |
| 21:36 | <@celticminstrel> | Okay, just to make sure I haven't missed anything here... to prove a problem M (in NP) is NP-complete, I need to show that a known NP-complete problem H is polynomially reducible to M, which just means giving a polynomial time algorithm that computes H using M as a subroutine, right? |
| 21:36 | <&McMartin> | I'm a little sleep deprived but I believe that is half of it |
| 21:36 | <&McMartin> | That proves that it is NP-Hard |
| 21:36 | <&McMartin> | To be NP-Complete you must additionally prove that M is in NP itself. |
| 21:37 | <@celticminstrel> | "to prove a problem M (in NP) is NP-complete" |
| 21:37 | <&McMartin> | Oh, whoops |
| 21:37 | <&McMartin> | Yeah |
| 21:37 | <@celticminstrel> | (Proving it's NP was the previous question.) |
| 21:37 | <&McMartin> | Then that's all you need. |
| 21:37 | <@celticminstrel> | Okay. The way the question was stated made it sound a bit more complicated. |
| 21:37 | <&McMartin> | Just make sure you don't do it in reverse~ |
| 21:38 | <@celticminstrel> | In reverse? |
| 21:38 | <&McMartin> | The fact that M is in NP means that you prove nothing by reducing M to a known NP-Complete problem. |
| 21:38 | <@celticminstrel> | Giving an algorithm to compute M using H has a subroutine? |
| 21:38 | <@celticminstrel> | ^as a |
| 21:38 | <&McMartin> | Yeah |
| 21:38 | <&McMartin> | Which you are guaranteed to get and which proves nothing, what with M being given as in NP and H given as NP-Complete |
| 21:39 | <@celticminstrel> | I think that would be an easy mistake to make. |
| 21:39 | <&McMartin> | Yes, hence my warning! |
| 21:39 | <@celticminstrel> | Heh. |
| 21:41 | | macdjord|slep is now known as macdjord|out |
| 21:44 | | gnolam [lenin@Nightstar-lgrapr.tbcn.telia.com] has joined #code |
| 21:44 | | mode/#code [+o gnolam] by ChanServ |
| 21:49 | <@Reiv> | It's been long enough since I played with NP that I don't actually understand that warning. |
| 21:54 | | * McMartin eyes Subversion 1.8 |
| 21:54 | <&McMartin> | ... patch would have called that diff a conflict but you got it right. What is this sorcery? |
| 21:58 | <@Tamber> | Don't be daft, it's not the first of April yet. |
| 21:58 | <@Tamber> | ;) |
| 21:59 | <&McMartin> | Indeed it's not, hence my confusion! |
| 21:59 | <&McMartin> | It also appears to be basically unusable without ssh-agent now |
| 22:16 | <&ToxicFrog> | Reiv: so, a problem M in NP is NP-Complete if you can convert any other problem in NP into an instance of M in polynomial time. |
| 22:16 | <&ToxicFrog> | Subset-sum and traveling salesman are well known NP-Complete problems. |
| 22:17 | <&ToxicFrog> | An easy way to problem that some other problem N is NP-Complete is (a) whoops, time to head home |
| 22:17 | <&ToxicFrog> | I will explain when I get there~ |
| 22:23 | <@macdjord|out> | Alas, he has a marvelous algorithm for this, but this channel is too narrow to contain it~ |
| 22:23 | <&McMartin> | s/channel/commute/ |
| 22:38 | | ErikMesoy is now known as ErikMesoy|sleep |
| 22:41 | <@celticminstrel> | WolframAlpha needs tooltips on its share buttons, because I have no intention of clicking a button whose meaning cannot be discerned. |
| 22:44 | <&McMartin> | That one is probably Pinterest or something~ |
| 22:47 | <@celticminstrel> | Hah, I clicked random and it didn't know how to interpret the input. XD |
| 22:48 | <@celticminstrel> | I don't know what any of those six buttons do. |
| 22:48 | <@celticminstrel> | The Share button and the ones next to it. |
| 23:01 | <@TheWatcher> | ... they do have tooltips for me |
| 23:02 | <@celticminstrel> | That's odd; they definitely don't for me. |
| 23:02 | <&ToxicFrog> | Reiv: ok, so, (a) prove that N is in NP, (b) prove that you can reduce M to N in polynomial time |
| 23:02 | <&ToxicFrog> | Because then you know you can reduce any problem in NP to N in polynomial time. |
| 23:03 | <&ToxicFrog> | Where you need to be careful is that, having proven (a), you have also implicitly proven that you can reduce N to M in polynomial time (because anything in NP can be reduced to M) |
| 23:03 | <&ToxicFrog> | So it's quite easy to get the proof backwards, prove that, and not actually prove anything new. |
| 23:03 | <&McMartin> | Also, the "fun" part, that is skipped in these proofs, is how you prove the "base case" - the first NP-complete problem you use as the standing point for everything else. |
| 23:04 | <&McMartin> | I think my algorithms class used SAT as the "core" NP-complete problem, and swiftly advanced to 3SAT |
| 23:04 | <&McMartin> | ("Given a statement of propositional logic without quantifiers, find an assignment of the variables that makes the formula resolve as true") |
| 23:08 | | * Tarinaky complains that there isn't enough stuff on P/NP/NP-Complete, Automata Theory or Big-O in his CS course. |
| 23:10 | < HotShot> | isn't this a one of those math paradoxes? |
| 23:10 | < HotShot> | p=np i think.... |
| 23:11 | <@Azash> | Tarinaky: Sipser and Cormen |
| 23:11 | <@Azash> | Hey presto |
| 23:11 | <@celticminstrel> | My professor started at 3SAT, while mentioning that the textbook does the proof for SAT. |
| 23:11 | <@celticminstrel> | So basically, he didn't prove the "base case". |
| 23:12 | <@Tarinaky> | I read an article a while back about how a universe where p=np would be a strange universe. |
| 23:12 | <@celticminstrel> | Oh? |
| 23:12 | | gnolam [lenin@Nightstar-lgrapr.tbcn.telia.com] has quit [[NS] Quit: gONE] |
| 23:12 | <@Tarinaky> | Don't remember exactly. |
| 23:13 | <@Reiv> | Yeah, I was trying to remember the bit where you had to be careful of proving backwards |
| 23:14 | | * Reiv did P/NP/NPComplete, Big-O and ... probably automata theory, which one is that |
| 23:15 | | * Tarinaky had like... 5 minutes of each crammed into a second year lecture between chantings of 'public static main void'. |
| 23:15 | < HotShot> | [04:37] <celticminstrel> "to prove a problem M (in NP) is NP-complete" |
| 23:15 | <@Azash> | Tarinaky: The two books mentioned above are well written and will get you a reasonable intro |
| 23:15 | <@Tarinaky> | Azash: I wish I had time and effort to read around my subjects atm. Too busy hurtling into a third D: |
| 23:16 | <@Tarinaky> | (English to Merica translation: low GPA) |
| 23:17 | <@celticminstrel> | Hm, HotShot? |
| 23:17 | < HotShot> | [06:13] <Reiv> Yeah, I was trying to remember the bit where you had to be careful of proving backwards |
| 23:18 | < HotShot> | was answering his question...? |
| 23:19 | <@celticminstrel> | How does quoting me answer his question? |
| 23:20 | < HotShot> | nevermind |
| 23:25 | <&ToxicFrog> | HotShot: why do you think that P=NP? |
| 23:25 | <&ToxicFrog> | Tarinaky: which course? Here that was spread over like 2-3 full semester courses |
| 23:26 | <@Tarinaky> | Computer Science and Mathematics Joint-Hons. |
| 23:27 | <&ToxicFrog> | Oh, so s/course/program/ |
| 23:27 | <@Tarinaky> | Oh god damn, I just broke my phone. |
| 23:28 | < HotShot> | i don't i thought you guys were talking about the "PvNP" paradox |
| 23:29 | <@Tarinaky> | Okay, that was weird. |
| 23:29 | <&ToxicFrog> | It's not a paradox and no, we were discussing ways to prove the NP-completeness of a problem |
| 23:30 | <&McMartin> | Right, which is standard, um, I don't know the UK equivalent |
| 23:30 | <@Tarinaky> | ToxicFrog: Umm... I have no idea what to answer. |
| 23:30 | <&McMartin> | In the US it's an upper-division theory course called something like Complexity and Theory of Computation |
| 23:30 | <&McMartin> | And, uh, course = class there >_> |
| 23:31 | < HotShot> | -.-' |
| 23:32 | <&McMartin> | And yes, a world where P=NP is one where any of our encryption algorithms that you can read legitimately in a decent amount of time you can also crack in a decent amount of time. |
| 23:32 | <&McMartin> | One-time pads are safe. I'm not really sure what else is. |
| 23:32 | <&ToxicFrog> | Tamber: here, a "course" is a class, typically taught for one semester, and a "program", "degree", or "degree program" is the set of courses and constraints that must be satisfied to graduate. |
| 23:33 | <&ToxicFrog> | Er, Tarinaky ^ |
| 23:33 | <&ToxicFrog> | So, "Theory of Computation" is a course, "Computer Science & Mathematics Joint Honours" is a degree program. |
| 23:33 | <@Tarinaky> | And you want me to tell you...? |
| 23:33 | | himi [fow035@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 23:34 | <&McMartin> | This was the textbook I learned this stuff from: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/11331877 9X |
| 23:34 | <@Tarinaky> | McMartin: In fairness, encryption being worthless is already true of a world where Quantum Computing is cheap so that's not /that/ remarkable... |
| 23:35 | <&ToxicFrog> | Tarinaky: what? You said "this course doesn't have enough <stuff>", I asked "what course" and you answered with your degree program |
| 23:35 | <&ToxicFrog> | So I assumed you meant the course list as a whole for it rather than any individual course |
| 23:35 | <@Tarinaky> | I see. Yes. The courselist as a whole. |
| 23:36 | <&McMartin> | Communication has been achieved, hooray |
| 23:36 | <@Tarinaky> | Are there actually any properly quantum encryption algorithms? (Quantum key-sharing doesn't count~) |
| 23:36 | <@Reiv> | Quantam Computing is going to continue being busted for a long time to come. |
| 23:37 | <@Tarinaky> | Reiv: So's P ? NP. |
| 23:37 | <&McMartin> | IIRC, QP != NP |
| 23:37 | <@Reiv> | It's much easier to extend bitlength than it is to extend bitcount in a processor; all you then need to do is ensure partial solutions aren't useful. |
| 23:37 | <@Tarinaky> | McMartin: Nope. But they both make classical encryption worthless. |
| 23:37 | <&McMartin> | You only get a polynomial-scale improvement with quantum algorithms. That's real, but it's not "have 256 cubits = bingo any SHA256 hash" |
| 23:38 | <@Tarinaky> | McMartin: Pretty sure there's an algorithm that actually does that. I'd have to check my notes for the name though. |
| 23:38 | <&McMartin> | Which is how it is often presented |
| 23:38 | <&McMartin> | There may have been advancements since the last time I attended any talks on the topic |
| 23:39 | <&McMartin> | At the time they were claiming a limit of "we can only divide complexity by O(n^2)" |
| 23:39 | <&McMartin> | Which doesn't get you out of exptime |
| 23:39 | <@Reiv> | McMartin: Which means you end up with, instead of eg 2^n, you enjoy 2^n-n^2 ? |
| 23:40 | <&McMartin> | (2^n)/(n^2) |
| 23:40 | <&McMartin> | Which is O(2^(n-2)) which is O(2^n) |
| 23:40 | <&McMartin> | well, no, I messed that up |
| 23:41 | <&McMartin> | But big-O notation removes a *lot* of extra terms, so I think subtraction and division of polynomials alike goes out in the wash |
| 23:41 | | * Reiv muses. Wishes he could remember how to do algebra to work out for n where (n^2) = (2^n)/(n^2) |
| 23:41 | <@Tarinaky> | McMartin: Well my lecturer suggested there was an algorithm for reversing mappings in constant time using something derived from Deutche's Algorithm. |
| 23:43 | <&McMartin> | That seems problematic to me if only because SHA->text is a one-to-many operation |
| 23:43 | <@Tarinaky> | http://en.wikipedia.org/wiki/Grover's_algorithm |
| 23:45 | <&McMartin> | "It provides a quadratic speedup" |
| 23:46 | <@Tarinaky> | Point. |
| 23:50 | | HotShot is now known as HotShot^Pizza |
| 23:58 | | Turaiel[Offline] is now known as Turaiel |
| --- Log closed Tue Apr 01 00:00:43 2014 |