Search found 649 matches

by Strilanc
Sun Jun 24, 2012 6:47 am UTC
Forum: Computer Science
Topic: Asymptotically-Optimal Algorithms to Decide NP Problems
Replies: 3
Views: 3001

Re: Asymptotically-Optimal Algorithms to Decide NP Problems

I don't know about optimal, but you can get arbitrarily close to optimal by using variations of the algorithm that takes polynomial time to solve NP problems if and only if P=NP . The constant factors are a bit absurd, though. The algorithm listed by wikipedia is a factor n away from optimal, since ...
by Strilanc
Wed Aug 11, 2010 6:29 pm UTC
Forum: Computer Science
Topic: Your best Fibonacci algorithm?
Replies: 24
Views: 11692

Re: Your best Fibonacci algorithm?

I derived a nice algorithm after I noticed this: - Let F(0) = [0,1] and F(1) = [1,0] - Then F(a+b) = F(a) dotproduct [F(b), F(b+1)] - And So F(2*n) = F(n) dotproduct [F(n), F(n+1)] Turning it into an algorithm, simplifying it, and translating it to something iterative gives: public static BigInteger...
by Strilanc
Fri Jul 30, 2010 6:12 pm UTC
Forum: Computer Science
Topic: Can you train a neural network to recognize prime numbers?
Replies: 35
Views: 17345

Re: Can you train a neural network to recognize prime number

Can you explain how a cyclic neural network can emulate a Turing machine. To be more precise, they can emulate finite state machines. But a large finite state machine is, in practice, the closest you will ever come to a Turing machine. For example, electronic computers are technically finite state ...
by Strilanc
Mon Jul 26, 2010 4:24 pm UTC
Forum: Computer Science
Topic: Can you train a neural network to recognize prime numbers?
Replies: 35
Views: 17345

Re: Can you train a neural network to recognize prime number

If the NN is feed-forward (i.e. no cycles) then it can only recognize a finite number of primes (it would have a maximum input size).

If the network can contain cycles, then you can use it to emulate a turing machine and any computable problem (including primality) is doable.
by Strilanc
Mon May 31, 2010 4:49 pm UTC
Forum: Computer Science
Topic: Thoughts on P = NP
Replies: 32
Views: 7969

Re: Thoughts on P = NP

LOL you computer scientists; isn't it obvious? P = NP is undecidable à la continuum hypothesis Seriously why hasn't anyone tried to show this yet? Now have a blast figuring out the implications of what I just asserted. And the best part is, since no one has settled the question, it has an equal pro...
by Strilanc
Fri Sep 04, 2009 6:30 am UTC
Forum: Individual XKCD Comic Threads
Topic: 0632: "Suspicion"
Replies: 112
Views: 37682

Re: "Suspicion" Discussion

How many years do you figure until this becomes a real problem?

I picture the eventual future of the internet being millions of fake websites populated by bots having believable and intelligent conversations about recent news events. And Pepsi brand cola.
by Strilanc
Mon Aug 31, 2009 4:52 pm UTC
Forum: Serious Business
Topic: eBay Sniping: Why does it even exist?
Replies: 29
Views: 7972

Re: eBay Sniping: Why does it even exist?

Based on what people have said, I believe it comes down to the fact that ebay reveals the second-highest bid. This reveals some information about the highest bid, which author bidders use to their benefit (and your detriment). In order to truly make sniping irrelevant I believe it would be necessary...
by Strilanc
Sun Aug 30, 2009 12:23 pm UTC
Forum: Serious Business
Topic: Patents... what are they good for?
Replies: 78
Views: 11490

Re: Patents... what are they good for?

Well, that's partly the fault of an incompetent patent board. Patent law states that patents should not be granted for something that's prior art (i.e. the obvious patents), and yet, because the bureaucrats at the patent office don't know anything about the current state of software innovation, the...
by Strilanc
Sun Aug 30, 2009 6:08 am UTC
Forum: Serious Business
Topic: Patents... what are they good for?
Replies: 78
Views: 11490

Re: Patents... what are they good for?

How have software patents not been mentioned yet? They're the perfect example of how to turn patents bad. The terms are too long relative to the pace of the industry, too many obvious patents are granted, and research costs are comparatively low (you generally don't need million-dollar equipment).
by Strilanc
Thu Aug 27, 2009 5:36 pm UTC
Forum: Serious Business
Topic: eBay Sniping: Why does it even exist?
Replies: 29
Views: 7972

eBay Sniping: Why does it even exist?

Ebay supports automatic bidding ( http://pages.ebay.com/help/buy/automatic-bidding.html ), meaning you pay what the second-highest bidder bids. But, if you only pay what the second highest bidder bids, there's no reason to snipe an action. You just bid the maximum amount you're willing to pay. After...
by Strilanc
Wed Aug 19, 2009 12:41 am UTC
Forum: Computer Science
Topic: What can i do with a computer science degree?
Replies: 31
Views: 64193

Re: What can i do with a computer science degree?

All things software are made by Computer Scientists, and plenty of things hardware too. Whenever your computer does something, except being powered off, a computer scientist told it to do so. Don't you remember when computers had to ask you to shut them off? ("It is now safe to turn off your c...
by Strilanc
Mon Aug 10, 2009 9:33 pm UTC
Forum: Serious Business
Topic: "As long as it doesn't harm anyone": bad argument?
Replies: 25
Views: 8597

Re: "As long as it doesn't harm anyone": bad argument?

The obvious reply to your friend is that they are doing harm, it's just not definite harm. For example there is a chance their long distance partner will discover the infidelity and be hurt emotionally. An action which truly has no negative consequences would by definition not be wrong, but there is...
by Strilanc
Mon Aug 10, 2009 9:10 pm UTC
Forum: Serious Business
Topic: What is Faith?
Replies: 58
Views: 7048

Re: What is Faith?

People who read a high school biology book and then get on here talking about how evolution is law have faith not very different to me then someone quoting bible verses as the word of god. I really agree with this. But I do think there is a difference between trust in a religion and trust in scienc...
by Strilanc
Mon Aug 10, 2009 6:27 pm UTC
Forum: Serious Business
Topic: What is Faith?
Replies: 58
Views: 7048

Re: What is Faith?

When someone says they have faith in something, it means they have confidence that it is true. It is not dependent on justification, and I don't think it requires a lack of justification either. That being said, saying "I have faith in X" is a very poor argument to convince people X is tru...
by Strilanc
Mon Aug 10, 2009 6:25 am UTC
Forum: Computer Science
Topic: Non-Algorythmic computing methods
Replies: 13
Views: 3404

Re: Non-Algorythmic computing methods

You do bring really interesting stuff tot he table, but then again the fact is not that the proof cannot be programmed, but if it is possible to make a program that can come up with the proof. So what argument can you give me to say that there can't be such a math? As far as I know the Halting prob...
by Strilanc
Sun Aug 02, 2009 11:15 pm UTC
Forum: Mathematics
Topic: log x
Replies: 36
Views: 4619

Re: log x

Any function called log should take the base as an argument. If you want base e, then call it 'ln'. Again, this all depends on what you use logs for. If you're a pure mathematician, especially some flavor of analyst, the only important logarithm is the natural one, and there's no point in talking a...
by Strilanc
Sun Aug 02, 2009 1:08 pm UTC
Forum: Mathematics
Topic: log x
Replies: 36
Views: 4619

Re: log x

For my purposes: log depends on the context. I usually use it to mean base 10. lg is base 2 ln is base e I hate it when standard libraries use 'log' to mean log_e precisely because the base isn't standardized. Any function called log should take the base as an argument. If you want base e, then call...
by Strilanc
Fri Jul 31, 2009 3:24 am UTC
Forum: Logic Puzzles
Topic: Spherical Poker
Replies: 6
Views: 2618

Re: Spherical Poker

Confirming douglasm's result. Reasoning: Consider player 1's probability-to-call function f. This function can be divided into area below player 2's threshold L, and the area above it. Let's consider what happens when we keep the area on each side of L constant, but move the probabilitie...
by Strilanc
Thu Jul 30, 2009 9:49 pm UTC
Forum: Logic Puzzles
Topic: Spherical Poker
Replies: 6
Views: 2618

Re: Spherical Poker

+3/8 is pretty good, but I have a strategy that achieves +5/9. I believe I can prove it's optimal, as well. *edit* Bah. Math error. It comes out to +1/3, which is lower. I'm still trying to figure out why it's lower, though. The formula for player 1's expected value, given player 1&...
by Strilanc
Thu Jul 30, 2009 4:34 am UTC
Forum: Logic Puzzles
Topic: Spherical Poker
Replies: 6
Views: 2618

Spherical Poker

Try to analyze an extremely simplified version of poker. I made it relatively far, but ran into a wall just when I was getting close to the meat. The game: - Each player is given a uniformly random real number between 0 and 1. They do not initially reveal these values to the other player. - The seco...
by Strilanc
Mon Jul 20, 2009 4:49 am UTC
Forum: Individual XKCD Comic Threads
Topic: 0612: "Estimation"
Replies: 109
Views: 27281

Re: "Estimation" Discussion

This is a big problem everywhere. I've never seen a program give good time estimates. The worst part is they give no indication of the uncertainty. Sometimes the times are given down to the second when there are still hours left! A more proper estimate would be a range, like "between 2 and 5 ho...
by Strilanc
Thu Jul 16, 2009 10:49 pm UTC
Forum: Logic Puzzles
Topic: Infinite Minesweeper
Replies: 42
Views: 4936

Re: Infinite Minesweeper

I can definitely improve Yak's upper bound. Divide the board into 2x2 blocks. Adjacent non-empty 2x2 blocks will create a solid border in minesweeper (unlike adjacent non-empty 3x3 blocks). The probability that a 2x2 block will be non-empty is p2 = 1 - (1-p)^4. When p2 exceeds the pe...
by Strilanc
Wed Jul 15, 2009 11:26 pm UTC
Forum: Logic Puzzles
Topic: Infinite Minesweeper
Replies: 42
Views: 4936

Infinite Minesweeper

Suppose you have an minesweeper board unbounded in both height and width. Each cell on the board is a mine with probability p, otherwise an empty cell. What is the probability that there is an empty region which trivially separates all the mines into finite sets (using the algorithm most minesweeper...
by Strilanc
Mon Jul 06, 2009 11:29 pm UTC
Forum: Gaming
Topic: Portal! WILD MASS GUESSING AND THEORIZING AND BULLSHIT!
Replies: 423
Views: 74117

Re: Portal Secrets and Storylines? - ***spoiler warning***

GlaDOS is totally untrustworthy. Everything it says is to manipulate you, not to inform you (also to be funny). I wouldn't put much thought into deciphering the truth or hidden meanings of what is said. As for the story, I assumed a previous test subject made it as far as the big room at the end. Th...
by Strilanc
Wed Jul 01, 2009 12:42 pm UTC
Forum: Computer Science
Topic: Beating the anti-bot letter-images
Replies: 16
Views: 3141

Re: Beating the anti-bot letter-images

Even if you have a really-trulio-unbreakable captcha, the solving work can be outsource to a country where labour is dirt cheap.

I figure pretty soon you'll have to pay some company to provide you with an ID you can use on websites.
by Strilanc
Sat Jun 27, 2009 9:23 pm UTC
Forum: Logic Puzzles
Topic: Higher dimensional tic-tac-toe
Replies: 8
Views: 4719

Re: Higher dimensional tic-tac-toe

Generalize! An (n, p) game of tic-tac-toe is played on an n-dimensional board ({0,1,2}^n) with m players. How many players are required in general to force draws? Does there exist an (n, p) such that perfect play doesn't result in a draw or the first player winning? If not, what if the other players...
by Strilanc
Tue Jun 23, 2009 5:24 pm UTC
Forum: Computer Science
Topic: Thoughts on P = NP
Replies: 32
Views: 7969

Re: Thoughts on P = NP

Feynman when he was first told of this problem was shocked that it was still an open problem - he thought it was obvious that P!=NP I'm inclined to agree, but a formal proof would be nice. The class P/NP problem: finding a specific leaf in a binary tree which is totally random. Deterministic algori...
by Strilanc
Thu Jun 18, 2009 5:43 am UTC
Forum: Computer Science
Topic: What would you do with an infinitely fast computer?
Replies: 818
Views: 226424

Re: What would you do with an infinitely fast computer?

If you've got an infinitely fast computer, cryptosystems fall into two categories: those that are broken, and those that are one-time pads. A perfect OTP generates a uniform set of possible plain text outputs over all bit strings of the length of the OTP system. One could generate a cryptosystem th...
by Strilanc
Wed Jun 17, 2009 7:09 pm UTC
Forum: Computer Science
Topic: Consequences to P=NP
Replies: 41
Views: 8763

Re: Consequences to P=NP

zalzane wrote:is 1 a whole number?

P=NP

P=5 (or any other whole number)
N=1

5=(1)(5)


If that's a joke, it's correct but not particularly funny.
If that's not a joke, it's hilarious but not correct.

You see the bind I'm in? I don't know what to critique and what to praise.
by Strilanc
Thu Jun 11, 2009 6:02 am UTC
Forum: Science
Topic: Our bodies all have the same chirality. Isn't that weird?
Replies: 53
Views: 6797

Re: Our bodies all have the same chirality. Isn't that weird?

Would it be possible to create bacteria of the opposite chirality, but who one-way switch the chirality of "our" molecules so they can consume them?

We might not want to create that particular type of bacteria.
by Strilanc
Wed Jun 10, 2009 2:26 pm UTC
Forum: Serious Business
Topic: Rejecting disease treatment for aesthetic purposes.
Replies: 46
Views: 6017

Re: Rejecting disease treatment for aesthetic purposes.

I wonder what the moral ramifications of shaving her head without her permission are.
by Strilanc
Wed Jun 10, 2009 2:20 am UTC
Forum: Science
Topic: Our bodies all have the same chirality. Isn't that weird?
Replies: 53
Views: 6797

Re: Our bodies all have the same chirality. Isn't that weird?

The wiki article was great, thanks! Apparently less than one in ten thousand people have it.
by Strilanc
Wed Jun 10, 2009 2:18 am UTC
Forum: Serious Business
Topic: Rational actors are really rational, like it or not.
Replies: 113
Views: 8625

Re: Rational actors are really rational, like it or not.

That's the 2 unstable points. It's a game that doesn't Qualify for a Nash Equilibrium, Like the Traveler's Dilemma Please read more than Wikipedia before trying to 'explain' it to me. A lot of the way you talk is using a very layman terms broad usage of words you don't quite mentally follow. A lot ...
by Strilanc
Wed Jun 10, 2009 1:23 am UTC
Forum: Science
Topic: Our bodies all have the same chirality. Isn't that weird?
Replies: 53
Views: 6797

Our bodies all have the same chirality. Isn't that weird?

Your heart is on your left, your liver is mostly on the right, and so on. I've never heard of anyone with opposite chirality, ie. heart on the right, liver on the left, and similar reversal for everything else above the the cellular level. Isn't that odd? We take it for granted, but it's surprising ...
by Strilanc
Mon Jun 08, 2009 3:00 pm UTC
Forum: Coding
Topic: Iterators in VB10
Replies: 0
Views: 498

Iterators in VB10

How many people have tried out the vb10 beta? I'm enjoying multiline lambdas way too much to be healthy. Implicit line continuations are *amazing*. I did a search ", _" and replace "," and took out 1000 characters of cruft (*don't do this unless you know none of your function cal...
by Strilanc
Sun Jun 07, 2009 2:45 am UTC
Forum: Serious Business
Topic: Rational actors are really rational, like it or not.
Replies: 113
Views: 8625

Re: Rational actors are really rational, like it or not.

The "rational actor", up against another "rational actor", must claim $2 because it's always better to pick $99 than $100, with $100 out of the picture it's always better to pick $98 than $99, and so on. The "rational actor", up against another "rational actor&quo...
by Strilanc
Sat Jun 06, 2009 9:38 pm UTC
Forum: Serious Business
Topic: Rational actors are really rational, like it or not.
Replies: 113
Views: 8625

Re: Rational actors are really rational, like it or not.

There is a very good reason people don't always pick the 'rational' choice when faced with games: we're hardwired to consider the game as part of a larger iterative game. We're so hardwired that we have a hard time accepting it's even possible for 2$ to be the rational answer to the traveler's dilem...
by Strilanc
Fri Jun 05, 2009 8:05 pm UTC
Forum: Computer Science
Topic: Is this an NP Problem? Is there a better solution?
Replies: 10
Views: 1756

Re: Is this an NP Problem? Is there a better solution?

Much better: (a or ~b or c) and (~a or c or ~d) and (a or d or e) Specify null char: ___ ___ ___ __ __ __ __ __ __ __ __ = 0 Specify flipflops: ___ ___ ___ __ __ __ TF __ __ __ __ = 1 ___ ___ ___ __ __ __ FT __ __ __ __ = 1 ___ ___ ___ __ __ __ __ TF __ __ __ = 1 ___ ___ ___ __ __ __ __ FT __ __ __ ...
by Strilanc
Fri Jun 05, 2009 7:30 pm UTC
Forum: Computer Science
Topic: Is this an NP Problem? Is there a better solution?
Replies: 10
Views: 1756

Re: Is this an NP Problem? Is there a better solution?

*edit* Bah, I found an error. But it should be relatively trivial to work it out form here: Suppose we have a 3-sat instance: (a or ~b or c) and (~a or c or ~d) and (a or d or e) identify null char: ___ __ __ __ __ __ = 0 create true-false restrictions: ___ FT __ __ __ __ = 1 ___ __ FT __ __ __ = 1 ...
by Strilanc
Fri Jun 05, 2009 5:47 pm UTC
Forum: Logic Puzzles
Topic: Camels and Bananas
Replies: 27
Views: 5793

Re: Camels and Bananas

You can do 4000 with 421236 bananas VB6: (note: \ is truncation integer division) Private Function MoveDistance(ByVal d As Long, Optional ByVal c As Long = 1000) Dim b As Long Dim db As Long While d > 0 db = 2 * ((b + db) \ c) + 1 'un-eaten b = b + db d = d - 1 We...

Go to advanced search