1) Thinking you might make out with someone later can get you through a day full of crappy java code, but then when it doesnt happen, again, well your life sucks all that much more, especially if you no longer have a motorcycle to burn off all the energy with. Not that the highways here are that great anyway--too many places for cops to hide. I might try to look into some kind of gas grenade for evasion, but at those speeds I would have to launch it in front of me and ride through it. Thats a lot of gear anyway.
2) Programmers who completely rewrite a bunch of data classes, and who leave the old set because it can't be removed, should write the damn converter when they write the new ones. That way, people like me won't be stuck trying to make sense of the mess later.
3) Code should be written to die honorably. Code should not be written to live forever like they teach you in programming class. Code that is designed well can be easily replaced, taken out back, and shot. Code that is not designed well lives on because it is an undead zombie and you can't take it out without the coding equivalent of a double barreled shotgun, which requires destroying (i.e. rewriting) a lot of otherwise-innocent code in the process.
Also, FYI, this isn't really for any of you; I just wanted to clear some space on my whiteboard for this unnecessarily complex class diagram. Seriously--we have 3 data types, but I'm already at 8 different java classes and still counting....
Thursday, May 20, 2010
Wednesday, May 19, 2010
Nightingale in a Golden Cage
A nightingale in a golden cage
That's me locked inside reality's maze
Come someone, make my heavy heart light
Come undone, bring me back to life
That's me locked inside reality's maze
Come someone, make my heavy heart light
Come undone, bring me back to life
Last night (monday) my actually unfinished 3-sat solver correctly identified as solvable or unsolvable every problem I threw at it. All...ten of them. Tonight I spent somewhere near three hours writing java code to unzip and untar files in memory because all of the benchmark 3-Sat problems from satlib.org were compressed, and I was on my windows laptop, and windows fails at compression (as well as everything else) and the copy of 7 zip I downloaded was...something weird was going on with it. Oh and I was also writing and debugging a .cnf parser. Cnf files are text files containing 3-sat problems and they decided to use "c" instead of "#" for comment lines. They also decided to have lines containing just a "%" which the website with the cnf specification didn't tell me about. I had a lot of fun running back and forth between my windows laptop with my broken cnf parser and my linux desktop that could actually read the files. You might be wondering why I didn't just work on the program on my linux box. I'm sure there was a good reason.
Also, by the way, none of the zip compression libraries for java (that I found) provide any useful means of answering the question "is this a gzipped file?" or "is this a tar file?" They expect you to know ahead of time. I searched for something like "java identify a gzipped file" and found nothing but websites enumerating various fallible file name conventions, with helpful tables for stupid people that contained entries like ".gz | this is a gzip file." Except that any idiot could rename a .png to a .gz, rendering your ignorant table invalid. So then I decided my test program just had to automatically and correctly identify the file type now matter what file I gave it, because that is like the bare minimum a good program would do.
But no one on the internet seemed to share that opinion. In fact if you googled for "java correctly identify a gz file" you might think the world was run by ignorant windows users. Apparently everyone else thinks its cool to just assume that the suffix in the name of the file is somehow related to its contents. Because idiots could never rename a file. So I started doing it on my own. I got about 90% through RFC 1952 when I decided that relying on the filename would be just fine.
So then I began testing my solver against real data. I gave it a score of known satisfiable problems and it told me they were satisfiable. Then I gave it a score of known unsatisfiable problems and it told me...they were all satisfiable. I was defeated by a tiny little file called uuf50-0218.cnf. Actually, its not that tiny. It has like two hundred lines, which I now have to analyze exhaustively to understand why it isn't satisfiable. It looks satisfiable to me. This problem involves 50 variables, which means using my algorithm to solve it by hand will requir about...125,00 cardboard boxes from staples. That can't be right. There's only 200 clauses in the entire file. Ok, so I'm going to need 200 boxes.
You could say I completely underestimated 3-sat. And I don't know why my approach doesn't work. I have to know, and more importantly I have to see it. This may require building some kind of 3d 3-sat exploration program that will project the hypercube into various sets of 3 dimensions, letting you navigatie it like a boolean version of Han Solo. "I solved 3-sat in less than 9 arc-seconds!" However, watching my dumb little program fail to solve what is probably every single problem in the sample unsatisfiable set was enough to kill my motivation. Maybe this will become like a hobby or something. I just need to learn how to excercise some modicum of self control when I think about this problem, and finish the part that actually prints the solution. On the bright side, this was less painful than pining after some girl.
In other news, my day job has suddenly become boring. I think I convinced myself that it wasn't boring before, for some combination of 3 reasons: 1) it didn't involve painful and frustrating projects with the worst code I've ever seen and wasn't allowed to fix, 2) I left almost all of my friends and various other hundreds of people that I actually liked talking to (or dancing with) and moved 2,000 nautical miles away to a city where the fucking people wait to cross the street even if no cars are coming and 3) people keep asking me how I like it out here and if I like my job, and I don't like telling them it sucks. Well, it doesn't suck but its very boring. From a computer science point of view, a lot of the code I work on literally does nothing. Nothing important. Like if you were going to write down the algorithm in math, you would have an empty piece of paper after skipping all the unimportant parts. Programming in large companies seems to drown you in the unimportant parts. We are shoveling data around, mapping from one poorly designed, legacy/deprecated/the-guy-who-wrote-the-code-is-gone data format to another. Or maybe I'm ninja-ing the existing, crappy design of a piece of software into what was a nice, new design for a piece of software because we can't get rid of the old one. Or maybe I'm scheduling "deployments" of this crappy messaging software that I'm supposed to manage that my team didn't write and has no control over, but which has the power to bring our system down. Then there's all the damn bugs in the system that I probably shouldn't be mentioning it here. Most of them involve some team we've never heard of making a major screwup, which is not detected until the data goes through a ton of systems and ends up at ours, and then blows up. There is a phrase for getting paged in the middle of the night because someone else's mistake broke your software, which you must keep running. We call it "operational pain." Another description that comes to mind is "bullshit." Also my boss is actively trying to get me to take more responsibility, and develop more cross-team interpersonal whatever skills, and like fifty other things that don't make me a better programmer--just a better drone.
This has caused me to ask the question: is there any substance on earth that can remove boredom? I drink a lot of caffeine at work so I don't fall asleep at my desk, but while it inhibits sleep it doesn't make anything I do more interesting. Every other mind-altering substance on the planet sounds like it would ruin my ability to concentrate.
Sometime I get to write code. But unless I'm working on some side project, as in, something I'm not supposed to spend time on but can get away with because I'm pretending to do it on my own time, then I have to be writing code using these ancient, overdesigned and poorly designed libraries with in-house developed tools that...well, they make Eclipse look like a good development tool. Imagine standing up a brand new service, and as soon as you run it, it starts spitting out, to the log file, a hundred useless and unwanted lines of crap per minute, and thats normal. So no, I don't like my job. 3-Sat has probably just made me hate it, in fact. I don't like staring at my screen wondering how this next piece of undocumented crap I'm supposed to use works. And the money isn't that great. I have about the same commute as when I worked in Philly, and I'm still breaking even money wise; the only difference is the federal government is stealing a higher percentage. I wish I could just take things from people. "Oh thats an awfully nice car you have there. I'll have a third of it. Nice house! My agents will be here in April to remove that south wing." I'd love to find out how all this tax money gets wasted, but every damn time I talk about politics with anyone, someone comes at me with some oddball claim I've never heard of that forces me to experience cognitive dissonance when their story contradicts everything I've ever heard on a subject. Oh, you think Cuba is a panacea of medicine fields? That's totally plausible. Or you're claiming some ridiculously bold conclusion about the Puritans/Pilgrims based on some audio book that conflicts with the history channel documentary I saw when I was up all night being sick from The Cheesecake Factory. Or you just trump me by taking the conversation to some minute cultural detail of a country I've never been to. Or you look down upon all religions, but you also look down upon other people that look down upon other religions, but you yourself believe in ghosts. Thats fun. I wonder if I could memorize a set of trigger phrases that could turn every conversation into a heated debate about something. I could be like a conversation ninja, darting from group to group of people, assasinating all non-useless discussion. I guess I really shouldn't complain; I used to read slashdot.
We played volleyball tonight as well. My team lost every game. I think if we work hard enough we may have a shot at being the worst team in the league. I actually just caught the ball once, after only two hits, because I didn't feel like flailing at it and sending it way out of bounds. My team didn't like that. Whatever. We lost anyway. Its depressing to realize that you are so bad you get intimidated when the other team has mastered fundamentals like bumping, setting, and not hitting the ball wildly out of bounds on your first hit.
Oh, and I walked by that dance studio across the street during one of my mad dashes into the outside world for some food. I caught a glimpse that one girl I was interested in. I think I called her red shirt girl here. Apparently she is still on that dance team thing. I'm not sure how this affects me. I was talking to one of my female friends out here after she'd had a bit of wine and discovered that I still lack the ability to determine if a girl is interested in me. I mean, I can determine if she's interested...just not in polynomial time.
Monday, May 17, 2010
Depth-First Insanity (DFI)
I've been going since maybe Friday night without finding an hole in my solution. I've run through the algorithm on paper, and by paper I mean a series of cardboard cubes scattered around my apartment. I took some pictures; I'll try to upload them here sometime. Actually they are not just cardboard. I don't know if you know this, but projecting a hypercube into 3 dimensions requires twice as many physical cubes every time you add a dimensions. Suffice to say I need a lot of cubes.
The first cube was constructed by taping a box of jello mix onto a box of pudding and slapping some paper on time. Then I needed a cube in four dimensions, which means I needed two cubes: one for positive w and one for negative w (the first 3 dimensions are x,y and z). If this doesn't make sense to you, stop reading now. So anyway I had ordered a video converter so that the next time Firefly girl and I watch Castle I can go to her place and play the videos from my laptop. Anyway, so I spent like an hour or two cutting up this box at work. Now I had a cube for w and a cube for !w. Well, then I added the A dimensions, so I had to go up to four cubes. But then I wanted to add the B dimensions, but I had already put stickers all over my x-y-z-w-a cubes in case anyone wanted to come over and check out my hypercube (no one does) so then I needed 8 more cubes. And after that I realized that my data structure was growing exponentially, and I needed to start analyzing various projections of the hypercube into 3 dimensions. Like, for a hypercube with dimensions x,y,z,w,a,b, I wanted to look at a cubic projection of x,y,z, and y,z,w, and z,w,a, and w,a,b, etc.
So my quest to solve the hardest problem in computer science temporarily became a quest to find cube-shaped objects. I cut up a box of toothpaste and one or two other objects lying around my place and then left at like 2 am friday night to go to 7-11 in search of anything shaped like a cube. I tried to avoid all contact with other people, beacuse I knew the first words out of my mouth were going to be "do you have any cubes?"
Then I got to 7-11 and went on my search. It was down to condom boxes and bars of soap. I thought that using boxes of condoms would be funny, but it takes 4 of them to make a good cube shape, and i didn't want to be seen walking around with that many condoms. Instead, I elected for the boxes of soap because I actually needed soap. But then a guy who worked there saw me walking around with like--well, alot of--bars of soap and asked if I was going to some kind of soap party. I glanced at the awkward stack of soap towering from my arms to my neck and tried to figure out a way I could explain it, but eventually just settled on "its a long story," hoping he wouldn't take offense to my vaguery. I figured I'd rather him think I'm going to some kind of soap fetish orgy than explain what I'm actually going to do with it. That reminds me: I forgot to open up any of the boxes before I taped the paper over it ( the paper is for labeling the axis) so I'm actually still running out of soap.
Saturday I went to Staples and found a lot of $1 cardboard boxes that come in the perfect cube shape. I mean, as perfect as you can get without being that stuffed-animal cube thing from think geek. If I had known this was going to take more than a week I would have ordered a few. I also found this giant $30 tablet of poster-board-sized sheets of paper that you can use dry erase markers on. Then I got home and discovered that the tablet was actually just well-marketed and contained only a single dry erase surface, which I filled up immediately, as well as some giant sheets of paper I'll probably never use. All I really want are like posters--actually white posters that you can use dry-erase markers on. Whatever. I'm back on paper.
So Paul Oakenfold and me have been at this all weekend, save for tiny breaks like seeing Iron Man 2. There is a brief flash of a 4D hypercube, by the way, when Tony Stark is flipping through his fathers notebook. It actually makes no sense why there would be a hypercube in the notebook, but the entire subplot about synthesizing a new element actually makes no sense anyway. And I am starting to hear the same Oakenfold songs over again too many times. I may have to switch to Armen Van Buren. I need to wait until the algorithm is done though; I don't have nearly enough Armen Van Buren tracks to carry me the rest of the way.
Writing my solution in java turned out to be ridiculously tedious; it must be one of the most inefficient programs for transcribing algorithms. Everything is so simple in my head, and then I go to write it down and it turns into pages and pages of java code. Although, I did have to create some multi-dimensional cube-projection-thingy data structures, so I guess thats why.
I realize that the chances of me actually solving something that generations of smarter people have failed to solve are slim. The only things that make it plausible are the fact that most people think P != NP, and therefore aren't even trying, and the fact that maybe nobody loves hypercubes as much as I do. I actually tried to make a Neverwinter Nights campain involving a 4 dimensional tower. It was going to be awesome. Then I realized that 3^4 is 81, and the cool-looking gargoyle statues killed me every time I tried to playtest it, so I gave up.
I'm also skeptical that its possible for me to win a million dollars. Like that would change my life too much. I went for a walk today, though, to cool my brain off, and thought about what I could spend it on. There's always a plane capable of more than 300 knots so I can visit philly whenever I want. Then, I was thinking I'd buy the rights to Duke Forever and get that finished. Thats as far as I got. I actually don't care about the money as much as being able to write "solved 3sat in polynomial time" in the little application we use for reporting days off. I'm not excited though; I've been disappointed too many times to think I can actually solve this. The only reason I keep going is because I haven't failed yet. And because I can't think about anything else. Well, girls. But besides that I can't focus on anything else.
Anyway, I am mentally and even physically exhausted (lots of pacing around while playing with a deck of cards), as well as probably malnurished and dehydrated. I've had a lot of caffeine though. But I'm going to see this through. I just got to the fun part of the algorithm when I lost my concentration and had to call it a night. I'm gonna keep at it as soon as I get up tomorrow. I am so anxious too--at this point I won't really know if it works until I get the programming running and solve all possible 3-Sat problems with 4 and 5 variables--if I can. I remember that being a big number. I think 3-sat with less than 5 variables is a special case though.
If you posses any good sample data, feel free to send it to me. Better yet, send me a really big 3-sat problem that today's computers would take a week so solve, and we'll see how fast I can do it. My algorithm runs in about m^3 where m is the number of variables.
The first cube was constructed by taping a box of jello mix onto a box of pudding and slapping some paper on time. Then I needed a cube in four dimensions, which means I needed two cubes: one for positive w and one for negative w (the first 3 dimensions are x,y and z). If this doesn't make sense to you, stop reading now. So anyway I had ordered a video converter so that the next time Firefly girl and I watch Castle I can go to her place and play the videos from my laptop. Anyway, so I spent like an hour or two cutting up this box at work. Now I had a cube for w and a cube for !w. Well, then I added the A dimensions, so I had to go up to four cubes. But then I wanted to add the B dimensions, but I had already put stickers all over my x-y-z-w-a cubes in case anyone wanted to come over and check out my hypercube (no one does) so then I needed 8 more cubes. And after that I realized that my data structure was growing exponentially, and I needed to start analyzing various projections of the hypercube into 3 dimensions. Like, for a hypercube with dimensions x,y,z,w,a,b, I wanted to look at a cubic projection of x,y,z, and y,z,w, and z,w,a, and w,a,b, etc.
So my quest to solve the hardest problem in computer science temporarily became a quest to find cube-shaped objects. I cut up a box of toothpaste and one or two other objects lying around my place and then left at like 2 am friday night to go to 7-11 in search of anything shaped like a cube. I tried to avoid all contact with other people, beacuse I knew the first words out of my mouth were going to be "do you have any cubes?"
Then I got to 7-11 and went on my search. It was down to condom boxes and bars of soap. I thought that using boxes of condoms would be funny, but it takes 4 of them to make a good cube shape, and i didn't want to be seen walking around with that many condoms. Instead, I elected for the boxes of soap because I actually needed soap. But then a guy who worked there saw me walking around with like--well, alot of--bars of soap and asked if I was going to some kind of soap party. I glanced at the awkward stack of soap towering from my arms to my neck and tried to figure out a way I could explain it, but eventually just settled on "its a long story," hoping he wouldn't take offense to my vaguery. I figured I'd rather him think I'm going to some kind of soap fetish orgy than explain what I'm actually going to do with it. That reminds me: I forgot to open up any of the boxes before I taped the paper over it ( the paper is for labeling the axis) so I'm actually still running out of soap.
Saturday I went to Staples and found a lot of $1 cardboard boxes that come in the perfect cube shape. I mean, as perfect as you can get without being that stuffed-animal cube thing from think geek. If I had known this was going to take more than a week I would have ordered a few. I also found this giant $30 tablet of poster-board-sized sheets of paper that you can use dry erase markers on. Then I got home and discovered that the tablet was actually just well-marketed and contained only a single dry erase surface, which I filled up immediately, as well as some giant sheets of paper I'll probably never use. All I really want are like posters--actually white posters that you can use dry-erase markers on. Whatever. I'm back on paper.
So Paul Oakenfold and me have been at this all weekend, save for tiny breaks like seeing Iron Man 2. There is a brief flash of a 4D hypercube, by the way, when Tony Stark is flipping through his fathers notebook. It actually makes no sense why there would be a hypercube in the notebook, but the entire subplot about synthesizing a new element actually makes no sense anyway. And I am starting to hear the same Oakenfold songs over again too many times. I may have to switch to Armen Van Buren. I need to wait until the algorithm is done though; I don't have nearly enough Armen Van Buren tracks to carry me the rest of the way.
Writing my solution in java turned out to be ridiculously tedious; it must be one of the most inefficient programs for transcribing algorithms. Everything is so simple in my head, and then I go to write it down and it turns into pages and pages of java code. Although, I did have to create some multi-dimensional cube-projection-thingy data structures, so I guess thats why.
I realize that the chances of me actually solving something that generations of smarter people have failed to solve are slim. The only things that make it plausible are the fact that most people think P != NP, and therefore aren't even trying, and the fact that maybe nobody loves hypercubes as much as I do. I actually tried to make a Neverwinter Nights campain involving a 4 dimensional tower. It was going to be awesome. Then I realized that 3^4 is 81, and the cool-looking gargoyle statues killed me every time I tried to playtest it, so I gave up.
I'm also skeptical that its possible for me to win a million dollars. Like that would change my life too much. I went for a walk today, though, to cool my brain off, and thought about what I could spend it on. There's always a plane capable of more than 300 knots so I can visit philly whenever I want. Then, I was thinking I'd buy the rights to Duke Forever and get that finished. Thats as far as I got. I actually don't care about the money as much as being able to write "solved 3sat in polynomial time" in the little application we use for reporting days off. I'm not excited though; I've been disappointed too many times to think I can actually solve this. The only reason I keep going is because I haven't failed yet. And because I can't think about anything else. Well, girls. But besides that I can't focus on anything else.
Anyway, I am mentally and even physically exhausted (lots of pacing around while playing with a deck of cards), as well as probably malnurished and dehydrated. I've had a lot of caffeine though. But I'm going to see this through. I just got to the fun part of the algorithm when I lost my concentration and had to call it a night. I'm gonna keep at it as soon as I get up tomorrow. I am so anxious too--at this point I won't really know if it works until I get the programming running and solve all possible 3-Sat problems with 4 and 5 variables--if I can. I remember that being a big number. I think 3-sat with less than 5 variables is a special case though.
If you posses any good sample data, feel free to send it to me. Better yet, send me a really big 3-sat problem that today's computers would take a week so solve, and we'll see how fast I can do it. My algorithm runs in about m^3 where m is the number of variables.
Thursday, May 13, 2010
3SAT 2SAT MESAT YOUSAT
"Traveling Salesman has driven men to drink"
--Moshe Kam
--Moshe Kam
NP Complete and I go way back. Way, way back. Back before I knew that NP stood for "nondeterministic polynomial" and not "non-polynomial." This is how it usually goes:
First, I get some inspiration. Something someone else has probably tried before. Then I try it out, and it works. Yay! I start dreaming about what I'm going to do with the prize money for solving it while I set out to test my solution and then prove that it is polynomial. Then some little snag comes up. Some piece of the puzzle is either exponential, or wrong, and fixing requires adding an exponential algorithm. But I still think I've done it, so I spend the next few days or weeks trying to fix the problem. Every time I solve the exponential problem, some piece of that solution has its own, tiny exponential problem, and then that one has its own exponential problem, and eventually the problem I'm trying to tackle looks a lot like that thing in set theory where if you want to add a bunch of sets together you have to subtract the unions, but then you have to subtract the union-intersection from the unions, but you have to subtract the union-intersection-unions....and you have arrived at a problem that is exponential.
This time, it happened in roughly the same way. Except it started, like, monday, and its already thursday. Its like a drug. I can't pay attention in meetings because my mind is going over whichever little exponential snag is standing between me and one million dollars. And daydreaming about publishing a paper and using the letters "xkcd" for an example. This time, though, I came up against the set-union problem and backed up, and forced myself to completely rethink most of my solution.
In other words, I'm still in the rabbit hole. By not doing any work and using the whiteboard at my office, I've managed to, again, arrive at a solution that I think is polynomial but this time without using up all the paper in my apartment.
This time, though, I have little hope left for actually proving my solution. A week without adequate sleep, plus my caffeine overdose from last night is taking its toll, and I don't know how to prove my solution anymore.
I managed to establish this relationship between groups of expressions in 3SAT. That relationship was what was completely screwing me over all week but I managed to use it as an opportunity to prune the search space, allowing you to solve subproblems with fewer variables. I remember pruning having something to do with better run times, but all I really have is some vauge memory of my algorithms teacher writing something on the whiteboard.
So I'm going to keep going with this one, and if this last attempt fails I will give up. Until the next time. I'm not sure there will be a next time though; I can't imagine me ever getting closer than this. I mean, I made a hypercube out of two boxes. I can actually see the problem. It is likely that reason I always fail to solve the problem is that P!=NP and the solution I'm looking for doesn't exist. I have no clue how to prove that. I don't even understand the proof for why comparison sorting requires logarithmic time. One of the guys on my team here told me to use proof by contradiction...i.e. prove that it requires exponential time by assuming that it doesn't and failing to come up with an algorithm.
Man, what a rush. I think I stayed up all night tuesday because I was worried someone might solve it before I could.
Tuesday, May 11, 2010
3-SAT Got Me Again
I don't really remember what happened. It is 4:29 now as I write this. I'm pretty sure I've been working on 3-SAT since I got home, and I actually started this morning while I was at work. I don't remember what trigged it...I must have thought I had some kind of inspiration again.
For those of you who don't know what I'm talking about, there is this unsolved problem in computer science: the question is does P equal NP? Well, last time I checked it was unsolved. Its been more than a year since I was in grad school; maybe somebody's already done it. Anyway, to answer the question, you basically have to come up with an easy[1] way to solve the second-hardest[2] (or third-hardest, depending on how you count) problems in computer science, or prove that there is no easy way to solve them. I've heard most computer scientists are pretty sure that these problems have no easy solution, but can't prove it.
After probably 10 or 12 hours on this attempt, I am pretty sure that I will eventually come up with a solution, one way or the other, but I can't prove it. The only thing that makes this attempt different than the others is I'm not trying to come up with a polynomial time algorithm (i.e. the easy way) to solve it. This time, I thought I would just attempt to solve every instance of 3-Sat (for 4 variables) and, you know, see where that took me. You may not know this, but there are a lot of instances of the 3-Sat problem for 4 variables. Like, if you wrote down how many possible 3-Sat problems with 4 variables there are, that number would probably have more than 17 digits. I don't know for sure though. Combinatorics is not my strong spot. In fact I have been cheating and using a calculator.
So, anyway, I did come up with a polynomial time algorithm. In fact, it might be damn near linear. The only problem is, you have to do this tiny little transformation to the 3-Sat problem--just a little...a little thing--and that itty bitty transformation happens to require exponential time (2^m where m is the number of variables in the problem, if you're curious). My giddiness at thinking I could actually be The One to solve P?NP gently faded like the slow realization that a girl doesn't have feelings for you and really can't even stand having you around.
If you're curious at what my solution was, I thought that 3-Sat expressions could be reduced to coordinates in m-dimensional space. More specifically, they are the coordinates for corners of a m-dimensional hypercube. If you fill all the corners, its not satisfiable. This would be a brilliant solution if m-dimensional hypercubes didn't have 2^m corners. So you can solve the problem, probably, just by counting the number of coordinates you get: if end up with less than 2^m coordinates, the problem is satisfiable. If you end up with 2^m coordinates, the problem is not satisfiable. And if you end up with more than 2^m coordinates...well that would mean I have no idea what I'm talking about. My next steps will involve writing lots of boolean expressions all over the place like a crazy man, and attempting to invent magic data structures.
In summary, I have this nagging suspicion that all of the satisfiable instances of 3-Sat can be solved in polynomial time, and all of the non-satisfiable instances of 3-Sat require exponential time to prove they are not satisfiable.
Oh, and if you don't know what a hypercube is, go here and buy this and mail it to me. You still won't understand hypercubes, but I'll have someone to sleep with at night.
[1] "easy way" = polynomial time algorithm
[2] NP-Complete
[Edit]
Here is the combinatorial calculator I've been using. Its actually awesome because it shows the formula.
Also, I did some thinking in the shower, and if there is a way to see if all of the corners on a single plane are required by the 3-Sat expressions in polynomial time, then we have it.
[Edit]
None of this really makes sense anymore. Its like I was high last night, but not really and I've actually never gotten high anyway. I don't know what I'm doing, but I think I can do it in polynomial time.
[Edit]
I am nearly certain I have a polynomial-time solution to 3-SAT. The proof is in my head; I should be able to translate it from English to Math by tomorrow. If I die before then, tell them the proof is on the wall of my apartment. Oh but not the apartment people--I used a sharpie and they're probably not gonna like that.
For those of you who don't know what I'm talking about, there is this unsolved problem in computer science: the question is does P equal NP? Well, last time I checked it was unsolved. Its been more than a year since I was in grad school; maybe somebody's already done it. Anyway, to answer the question, you basically have to come up with an easy[1] way to solve the second-hardest[2] (or third-hardest, depending on how you count) problems in computer science, or prove that there is no easy way to solve them. I've heard most computer scientists are pretty sure that these problems have no easy solution, but can't prove it.
After probably 10 or 12 hours on this attempt, I am pretty sure that I will eventually come up with a solution, one way or the other, but I can't prove it. The only thing that makes this attempt different than the others is I'm not trying to come up with a polynomial time algorithm (i.e. the easy way) to solve it. This time, I thought I would just attempt to solve every instance of 3-Sat (for 4 variables) and, you know, see where that took me. You may not know this, but there are a lot of instances of the 3-Sat problem for 4 variables. Like, if you wrote down how many possible 3-Sat problems with 4 variables there are, that number would probably have more than 17 digits. I don't know for sure though. Combinatorics is not my strong spot. In fact I have been cheating and using a calculator.
So, anyway, I did come up with a polynomial time algorithm. In fact, it might be damn near linear. The only problem is, you have to do this tiny little transformation to the 3-Sat problem--just a little...a little thing--and that itty bitty transformation happens to require exponential time (2^m where m is the number of variables in the problem, if you're curious). My giddiness at thinking I could actually be The One to solve P?NP gently faded like the slow realization that a girl doesn't have feelings for you and really can't even stand having you around.
If you're curious at what my solution was, I thought that 3-Sat expressions could be reduced to coordinates in m-dimensional space. More specifically, they are the coordinates for corners of a m-dimensional hypercube. If you fill all the corners, its not satisfiable. This would be a brilliant solution if m-dimensional hypercubes didn't have 2^m corners. So you can solve the problem, probably, just by counting the number of coordinates you get: if end up with less than 2^m coordinates, the problem is satisfiable. If you end up with 2^m coordinates, the problem is not satisfiable. And if you end up with more than 2^m coordinates...well that would mean I have no idea what I'm talking about. My next steps will involve writing lots of boolean expressions all over the place like a crazy man, and attempting to invent magic data structures.
In summary, I have this nagging suspicion that all of the satisfiable instances of 3-Sat can be solved in polynomial time, and all of the non-satisfiable instances of 3-Sat require exponential time to prove they are not satisfiable.
Oh, and if you don't know what a hypercube is, go here and buy this and mail it to me. You still won't understand hypercubes, but I'll have someone to sleep with at night.
[1] "easy way" = polynomial time algorithm
[2] NP-Complete
[Edit]
Here is the combinatorial calculator I've been using. Its actually awesome because it shows the formula.
Also, I did some thinking in the shower, and if there is a way to see if all of the corners on a single plane are required by the 3-Sat expressions in polynomial time, then we have it.
[Edit]
None of this really makes sense anymore. Its like I was high last night, but not really and I've actually never gotten high anyway. I don't know what I'm doing, but I think I can do it in polynomial time.
[Edit]
I am nearly certain I have a polynomial-time solution to 3-SAT. The proof is in my head; I should be able to translate it from English to Math by tomorrow. If I die before then, tell them the proof is on the wall of my apartment. Oh but not the apartment people--I used a sharpie and they're probably not gonna like that.
Thursday, May 6, 2010
Stormyball
After all the trouble I went through finding open volleyball gyms, some friends of mine invited me to do a league with them. It is at a "beach" called Golden Gardens. Our first game was Tuesday. Having not previously practiced together, we weren't all that great, but I discovered that by some cosmic glitch I still have the ability to serve. I had assumed that would have been the first of my skills to go after not playing for so many years, but when I tossed the ball up and hit it, it sailed right over the net with a touch of topspin. I still have to remember how to bump, set, spike, and block correctly, but I'm not worried about those.
The league has these rules where you have to have at least one girl on the court and no more than two guys. This bothers the part of my brain that tries to keep my views of the world consistent. Don't get me wrong: I think this rule would actually work great in many walks of life, from programming teams to ski lifts to road trips, to parties, to bars, dance classes, juries, lan parties, apartment buildings, bus stops, casinos, beaches, and hair salons, etc. What I don't get is having the rule on the volleyball court. I thought we were all saying that girls-can-do-everything-just-as-good-as-guys thing? Isn't that what we say now? Because of something about being modern now and leftover angst from the 50s? And the girls at Drexel getting pissy if I offered to walk them home?
According to complaints I've heard from the feminine gender, having a guy insinuate or even imply that he believes men are better at girls than something in some tiny way, even if its something most girls hate like playing Starcraft or deciding which Space Marine chapter more badass (I vote for either Blood Ravens or Blood Angels, although the Ultramarines have a pretty good shot), is one of the more grevious sins...something approaching rape or not using your turn signals to change lanes. So why is it that we tolerate having rules that demonstrate, in an ostensibly practical way, this philosophy? I don't know. I asked someone once--a girl, actually--and she whispered that guys play volleyball better or differently than girls, and we quickly drifted from the subject. What I do know, though, is that I don't really care, and I like making out more than making some kind of ill conceived stand for social consistency, so I'm going to go on with the "girls can do everything just as good as guys" thing, and try not to think about the glaring contradiction with the volleyball rules. If I have to choose between not condoning hippocracy and ever having sex, I know which side of the line I'm standing on.
That got me thinking, though. Can you actually compare two genders for something like volleyball? What does that even mean? Does every guy play volleyball better than every girl? No. Does every girl play better than every guy? No. If you took a random sampling of people, would one gender always be better than the other? No. You could, perhaps, get three (or two) of the best players from each gender to face off, but what would that prove? What if the guy team beats the girl team, but the average girl is better than the average guy? Would you have to start looking at percentiles? Normalize by years of experience, excepting those years spent in high school gym class because they play with screwy rules? Maybe try adding a ladder function to group the percentiles...but then you would need to subdivide by region and culture, oh and don't forget age, that will certainly throw you a curve, if you know what I mean. By the time you come up with a method, only people who have taken two probstat courses will even understand what you've done, and based on all the reality shows I've seen on the tv, that would be roughly no one.
I thought of this because I had the same problem when I asked if skiis are faster than snowboards. Actually I wasn't so much asking as arguing on the yes side. But I digress. There is no answer. There are many kinds of skiis, and many kinds of snowboards. Vis-a-vis (FINALLY!) there are many kinds of skiiers, and many kinds of snowboarders. There are many kinds of snow; in fact there are even different kinds of powder (wet, dry, man made, untracked...). Then there are all the different kinds of terrain. Moguls verses packed verses untracked powder verses cliffs verses half-pipes verses ice. You would have to factor all of that in. The only way, really, to answer the question is to throw one snowboarder and one skiier off of a cliff and have them fall all the way to the bottom, and see which one is more aerodynamic.
Oh, also, it rained. I'm no wimp; I've played volleyball in 40 degree weather at 2 am with crazy Drexel engineers with blinding lights on one side fo the courts and we had to let our feet go numb so they would stop aching. The rain, however, was kind of new. I didn't know you could play volleyball in rain. Also, the sand wasn't even that cold, but as soon as it got wet, my toes started going numb. It is a strange thing to be feeling raindrops in your head while tracking a volleyball with people wearing shorts and having your feet go numb. There's a lot of elements there that usually don't go together.
What's the important takeaway here? The moral of the story is I finally managed to use "vis-a-vis" in a sentance. I've been dying to figure out that phrase ever since I saw Matrix Reloaded but couldn't before because I didn't understand what it meant and never had both motive and opportunity. Well now. I'm going to sleep good tonight.
Also, after careful consideration I think there should be only one guy allowed in the entire league: me. Everyone else has to be a girl between the ages of....20.0 and ...oh yuck way less than 38. And everyone has to drink when we switch sides. And the winning teams from last week dress like pirates and have to scream "gyarrr!!!" when they serve or it doesn't count.
[Edit]
In other news, Lego Capture-the-Flag??? I must try this. Red team and blue team, and guns and a simple arena, and when the lego men die they go to a timed prison, or respawn at certain points.
[Edit]
We wouldn't be able to use the normal brick wars rules...need to introduce entropy. Maybe only very short-range weapons, and roll dice to see which lego man dies? The lego men need to fight for multiple turns to keep things interesting.
[Edit]
make it a drinking game. After every flag capture, or maybe every time a lego man gets fragged, your opponent has to take a drink. It would be like beer pong but not retarded.
[Edit]
Also, I should celebrate my birthday in the summer. Just to throw people off.
[Edit]
Chris if you want to start with war with me, I want you to sit down for a moment and ask yourself a question. That question is: which one of us has more time on our hands to screw around on the internet? And I'm going to give you a hint. I just spent 40 minutes doing a painful interview over the phone for someone that was really bright but wouldn't make it past my colleagues' ridiculous interviewing standards, and I was so bored I started drawing a little lego man with his hands up in the air. Its actually pretty good; I might try to scan this even though its on ugly yellow worksheet paper. Thats not the point. The point is when I'm not coding I have a tendency to get bored and check the internet every 30 seconds, which includes reading my own blog when I run out of webcomics, so don't start another birthday war with me. I don't care if people know its the month of December. I just don't want them to know the exact date.
The league has these rules where you have to have at least one girl on the court and no more than two guys. This bothers the part of my brain that tries to keep my views of the world consistent. Don't get me wrong: I think this rule would actually work great in many walks of life, from programming teams to ski lifts to road trips, to parties, to bars, dance classes, juries, lan parties, apartment buildings, bus stops, casinos, beaches, and hair salons, etc. What I don't get is having the rule on the volleyball court. I thought we were all saying that girls-can-do-everything-just-as-good-as-guys thing? Isn't that what we say now? Because of something about being modern now and leftover angst from the 50s? And the girls at Drexel getting pissy if I offered to walk them home?
According to complaints I've heard from the feminine gender, having a guy insinuate or even imply that he believes men are better at girls than something in some tiny way, even if its something most girls hate like playing Starcraft or deciding which Space Marine chapter more badass (I vote for either Blood Ravens or Blood Angels, although the Ultramarines have a pretty good shot), is one of the more grevious sins...something approaching rape or not using your turn signals to change lanes. So why is it that we tolerate having rules that demonstrate, in an ostensibly practical way, this philosophy? I don't know. I asked someone once--a girl, actually--and she whispered that guys play volleyball better or differently than girls, and we quickly drifted from the subject. What I do know, though, is that I don't really care, and I like making out more than making some kind of ill conceived stand for social consistency, so I'm going to go on with the "girls can do everything just as good as guys" thing, and try not to think about the glaring contradiction with the volleyball rules. If I have to choose between not condoning hippocracy and ever having sex, I know which side of the line I'm standing on.
That got me thinking, though. Can you actually compare two genders for something like volleyball? What does that even mean? Does every guy play volleyball better than every girl? No. Does every girl play better than every guy? No. If you took a random sampling of people, would one gender always be better than the other? No. You could, perhaps, get three (or two) of the best players from each gender to face off, but what would that prove? What if the guy team beats the girl team, but the average girl is better than the average guy? Would you have to start looking at percentiles? Normalize by years of experience, excepting those years spent in high school gym class because they play with screwy rules? Maybe try adding a ladder function to group the percentiles...but then you would need to subdivide by region and culture, oh and don't forget age, that will certainly throw you a curve, if you know what I mean. By the time you come up with a method, only people who have taken two probstat courses will even understand what you've done, and based on all the reality shows I've seen on the tv, that would be roughly no one.
I thought of this because I had the same problem when I asked if skiis are faster than snowboards. Actually I wasn't so much asking as arguing on the yes side. But I digress. There is no answer. There are many kinds of skiis, and many kinds of snowboards. Vis-a-vis (FINALLY!) there are many kinds of skiiers, and many kinds of snowboarders. There are many kinds of snow; in fact there are even different kinds of powder (wet, dry, man made, untracked...). Then there are all the different kinds of terrain. Moguls verses packed verses untracked powder verses cliffs verses half-pipes verses ice. You would have to factor all of that in. The only way, really, to answer the question is to throw one snowboarder and one skiier off of a cliff and have them fall all the way to the bottom, and see which one is more aerodynamic.
Oh, also, it rained. I'm no wimp; I've played volleyball in 40 degree weather at 2 am with crazy Drexel engineers with blinding lights on one side fo the courts and we had to let our feet go numb so they would stop aching. The rain, however, was kind of new. I didn't know you could play volleyball in rain. Also, the sand wasn't even that cold, but as soon as it got wet, my toes started going numb. It is a strange thing to be feeling raindrops in your head while tracking a volleyball with people wearing shorts and having your feet go numb. There's a lot of elements there that usually don't go together.
What's the important takeaway here? The moral of the story is I finally managed to use "vis-a-vis" in a sentance. I've been dying to figure out that phrase ever since I saw Matrix Reloaded but couldn't before because I didn't understand what it meant and never had both motive and opportunity. Well now. I'm going to sleep good tonight.
Also, after careful consideration I think there should be only one guy allowed in the entire league: me. Everyone else has to be a girl between the ages of....20.0 and ...oh yuck way less than 38. And everyone has to drink when we switch sides. And the winning teams from last week dress like pirates and have to scream "gyarrr!!!" when they serve or it doesn't count.
[Edit]
In other news, Lego Capture-the-Flag??? I must try this. Red team and blue team, and guns and a simple arena, and when the lego men die they go to a timed prison, or respawn at certain points.
[Edit]
We wouldn't be able to use the normal brick wars rules...need to introduce entropy. Maybe only very short-range weapons, and roll dice to see which lego man dies? The lego men need to fight for multiple turns to keep things interesting.
[Edit]
make it a drinking game. After every flag capture, or maybe every time a lego man gets fragged, your opponent has to take a drink. It would be like beer pong but not retarded.
[Edit]
Also, I should celebrate my birthday in the summer. Just to throw people off.
[Edit]
Chris if you want to start with war with me, I want you to sit down for a moment and ask yourself a question. That question is: which one of us has more time on our hands to screw around on the internet? And I'm going to give you a hint. I just spent 40 minutes doing a painful interview over the phone for someone that was really bright but wouldn't make it past my colleagues' ridiculous interviewing standards, and I was so bored I started drawing a little lego man with his hands up in the air. Its actually pretty good; I might try to scan this even though its on ugly yellow worksheet paper. Thats not the point. The point is when I'm not coding I have a tendency to get bored and check the internet every 30 seconds, which includes reading my own blog when I run out of webcomics, so don't start another birthday war with me. I don't care if people know its the month of December. I just don't want them to know the exact date.
Saturday, May 1, 2010
Meeting Girls in Seattle
| show details 1:42 PM (1 hour ago)  |
Hey what kind of dancing do you like?
| show details 2:04 PM (38 minutes ago) |
hmmm..
this isn't the first time you've wrote me... does then name Jen Burchesky ring a bell? maybe I scared you off because I use aff I don't know, but we stopped talking.
Good luck in your search anyways...
Jen
this isn't the first time you've wrote me... does then name Jen Burchesky ring a bell? maybe I scared you off because I use aff I don't know, but we stopped talking.
Good luck in your search anyways...
Jen
| show details 2:18 PM (24 minutes ago) |
Well, if I did email you before google has no record of it. Unless,
of course, you responded saying you were on your roomates computer and
couldn't talk now but please check out this site with my pics on it.
Then I would have told google you're a spammer.
of course, you responded saying you were on your roomates computer and
couldn't talk now but please check out this site with my pics on it.
Then I would have told google you're a spammer.
- Show quoted text -
| show details 2:36 PM (6 minutes ago) |
hey its you! I'm just havin a chat on aff now so I'll write you back later tonight k? no wait a call would be better...I'm baked. lol
are you 420 friendly?
View My Photo Album
are you 420 friendly?
View My Photo Album
Subscribe to:
Posts (Atom)
