Wikipedia is right there.

If you need it dumbed down, NP is stuff like Sudoku: if someone shows you a solved Sudoku, you can check whether it is indeed solved without much effort, even if you don't know how to solve it yourself.

## Search found 671 matches

- Fri Apr 20, 2018 10:48 pm UTC
- Forum: Computer Science
- Topic: Formally, What is P and NP?
- Replies:
**19** - Views:
**7645**

- Fri Mar 16, 2018 6:07 am UTC
- Forum: Computer Science
- Topic: Looking for an algorithm to test for abridgement
- Replies:
**3** - Views:
**3488**

### Re: Looking for an algorithm to test for abridgement

You can do this in quadratic time with dynamic programming. As you go through the original book, word by word, keep track of all the possible corresponding positions you might be at in the possibly-abridged-book. Your list has at most linear size at each step, and updating it once takes at most lin...

- Sun Dec 10, 2017 5:17 pm UTC
- Forum: Forum Games
- Topic: The "Thread Necromancy" Game
- Replies:
**17190** - Views:
**1567406**

### Re: The "Thread Necromancy" Game

Finally!

- Tue Sep 26, 2017 11:38 pm UTC
- Forum: Mathematics
- Topic: A Set of Points
- Replies:
**2** - Views:
**2405**

### Re: A Set of Points

(-1,0) is not in your set. If we let ζ be a fifth root of unity, then every point in your set is an element of the ring Z[ζ] (that is, it can be written as a sum a + bζ + cζ 2 + dζ 3 + eζ 4 for some integers a, b, c, d, e). Algebraically, your rule 2 produces the point A + ζ(B-A) = (1-ζ)A + ζB, and ...

- Sat Jun 03, 2017 4:16 pm UTC
- Forum: Science
- Topic: Why do humans see themselves as different from animals?
- Replies:
**35** - Views:
**8907**

### Re: Why do humans see themselves as different from animals?

Step 1: Figure out why mice see themselves as different from other animals.

Step 2: Since humans are no different from mice, the answer will be the same.

Step 2: Since humans are no different from mice, the answer will be the same.

- Fri Jan 13, 2017 3:16 am UTC
- Forum: Mathematics
- Topic: N-player combinatorial game theory
- Replies:
**2** - Views:
**2102**

### Re: N-player combinatorial game theory

This is the only paper I've ever seen that does a decent job of exploring this kind of question. (In case of link rot: the paper is "Stable Winning Coalitions" by Daniel Loeb, and is part of Games of No Chance.)

- Thu Jan 05, 2017 11:43 pm UTC
- Forum: News & Articles
- Topic: The Thread To Remind Me We're Living In The Future
- Replies:
**1874** - Views:
**345337**

### Re: The Thread To Remind Me We're Living In The Future

Master was secretly AlphaGo all along . Reddit discussion: https://www.reddit.com/r/baduk/comments/5l3l7e/chinese_ai_crushing_pros_on_fox_server/ Life in 19x19 discussion: http://lifein19x19.com/forum/viewtopic.php?f=10&p=215117 Don't worry, the singularity is still a long way off.

- Sat Nov 12, 2016 5:58 am UTC
- Forum: Gaming
- Topic: HyperRogue
- Replies:
**1** - Views:
**1848**

### Re: HyperRogue

I secretly suspect the first level (the icy land) was originally made as a demonstration of the heat equation in hyperbolic space. The alchemist lab also seems like an excuse to show off percolation.

- Mon Sep 19, 2016 8:10 pm UTC
- Forum: Science
- Topic: Is entanglement that surprising?
- Replies:
**27** - Views:
**7673**

### Re: Is entanglement that surprising?

And if you've ever thought that quantum mechanical entanglement is cool, but doesn't go too far enough, check out Popescu-Rohrlich boxes.

- Tue Aug 02, 2016 9:41 pm UTC
- Forum: Mathematics
- Topic: Formula for the Volume of a n-cone
- Replies:
**20** - Views:
**5550**

### Re: Formula for the Volume of a n-cone

Do limits of Riemann sums fall under integral calculus? Because that's effectively what you're doing with your square mesh. Cavalieri's Principle, that the volume of a solid can be completely calculated by knowing its cross-sectional areas, is just a stone's throw away (no pun intended) from actual...

- Mon Aug 01, 2016 2:58 am UTC
- Forum: Mathematics
- Topic: Formula for the Volume of a n-cone
- Replies:
**20** - Views:
**5550**

### Re: Formula for the Volume of a n-cone

Both of the things you described here are things I would call "calculus". Really? To me, "calculus" has always meant "a symbolic method of calculation" (some variation of this definition is called for if you want to know why "propositional calculus", "la...

- Sat Jul 30, 2016 8:33 pm UTC
- Forum: Mathematics
- Topic: Formula for the Volume of a n-cone
- Replies:
**20** - Views:
**5550**

### Re: Formula for the Volume of a n-cone

There is no need for calculus. Just approximate the base of the cone with a bunch of little quadrilaterals (or hypercubes, in higher dimensions). In the two dimensional case, this is the same as breaking up a triangle's base into a bunch of smaller bases, cutting the whole triangle into a bunch of s...

- Mon Jul 25, 2016 10:13 pm UTC
- Forum: Mathematics
- Topic: Goahead52's Math Posts
- Replies:
**148** - Views:
**16956**

### Re: Factorials

This means that k! 2 +4n! must be a perfect square, Plugging in k = 2, we get an open problem . However, if we believe the abc conjecture then every solution has to have n pretty close to 2k: First, it's pretty clear that n has to be at least twice as large as the largest prime below k. Thus n can'...

- Mon Jun 20, 2016 3:15 am UTC
- Forum: Movies and TV Shows
- Topic: What would you do in a Groundhog Day scenario?
- Replies:
**9** - Views:
**5016**

### Re: What would you do in a Groundhog Day scenario?

First, I would read every book on my bookshelf. Then, read every book in every campus library. Then, read every book on library genesis. Then, read the entire internet, including the wayback machine. Next, I would take every piece of encrypted traffic I could get my hands on and break it via pure br...

- Tue May 24, 2016 7:38 am UTC
- Forum: News & Articles
- Topic: The Thread To Remind Me We're Living In The Future
- Replies:
**1874** - Views:
**345337**

### Re: The Thread To Remind Me We're Living In The Future

I do wonder where quantum computation will end up going, though. Mainly, if it'll ever find its place outside fundamental research and be something that plays in important role in your average Joe's life. For example, will a universal quantum coprocessor ever be a thing anyone would want in their P...

- Wed Feb 24, 2016 2:59 am UTC
- Forum: Coding
- Topic: IDEs and the death of the command line interface
- Replies:
**25** - Views:
**8577**

### Re: IDEs and the death of the command line interface

Hm, as an experiment, let's see what I have running right now . Two urxvt terminals (white text on black background) and gedit are running (gedit has ten files open - four cpp files, three txt files, one tex file, one bib file, and one file with no extension), as well as firefox, a file browser, and...

- Wed Feb 10, 2016 6:36 am UTC
- Forum: Mathematics
- Topic: INT Function
- Replies:
**13** - Views:
**2987**

### Re: INT Function

Here's something a bit more general: consider logical propositions you can build out of real variables, real constants, addition, subtraction, multiplication, division, comparison (equality or inequality), exponentiation, logical connectives (and, or, if, parentheses), and logical quantifiers (for a...

- Mon Feb 01, 2016 2:11 am UTC
- Forum: Logic Puzzles
- Topic: The Two Oracles - a statistics problem
- Replies:
**74** - Views:
**12979**

### Re: The Two Oracles - a statistics problem

But aren't b and c both necessarily 0? You can't both win and lose a war. Er... a+d is supposed to be the chance of what we observed so far happening, and b+c is supposed to be the chance of the opposite occurring, that is, one oracle claiming that we win the war and one oracle claiming tha...

- Sun Jan 31, 2016 10:44 pm UTC
- Forum: Logic Puzzles
- Topic: The Two Oracles - a statistics problem
- Replies:
**74** - Views:
**12979**

### Re: The Two Oracles - a statistics problem

Here are two boundary cases described in the framework where the oracles know the answers but sometimes screw up their answers on purpose. Let's pretend that the remainder of the Dow opening price modulo 1 is a uniformly random real number between 0 and 1. The first oracle checks tomorrow's ...

- Sat Dec 26, 2015 9:49 am UTC
- Forum: Logic Puzzles
- Topic: Escape the bear in the circle?
- Replies:
**22** - Views:
**5766**

### Re: Escape the bear in the circle?

Hehehehehehe

**Spoiler:**

- Mon Nov 02, 2015 2:55 am UTC
- Forum: Mathematics
- Topic: Divisor of the form an+1
- Replies:
**11** - Views:
**2823**

### Re: Divisor of the form an+1

The same argument works for a^n - b^n as long as a and b are relatively prime (the argument is fairly easy so that article left it out: just consider the order of a/b in the multiplicative group (mod q), note that this order must divide q-1, and that the order is n if q divides the nth cyclotomic polynomial evaluated at a/b but does not divide n). For the case of a^n + b^n, you should meditate on the problem yourself.Goahead52 wrote:The theorem 4 is about a^n-1 not a^n+b^n or a^n-b^n

I'm not sure how to parse this sentence.Goahead52 wrote:It is well known and the proof was yet given here.

- Sat Oct 31, 2015 11:27 pm UTC
- Forum: Mathematics
- Topic: Divisor of the form an+1
- Replies:
**11** - Views:
**2823**

### Re: Divisor of the form an+1

Check out this short proof of Zsigmondy's theorem, especially Theorem 4. I think it should answer your question.

- Fri Oct 16, 2015 11:11 pm UTC
- Forum: Serious Business
- Topic: Ethics of AdBlock
- Replies:
**639** - Views:
**125302**

### Re: Ethics of AdBlock

I'm a little disturbed by the claim that since most people are too apathetic about something to take action against it, there is automatically a social agreement that it is an ethically good thing. Imagine that there is a street you walk down every day (maybe it is a street connecting your home to a...

- Mon Sep 28, 2015 1:58 am UTC
- Forum: Mathematics
- Topic: Theoretical problem about traveler salesman
- Replies:
**6** - Views:
**1976**

### Re: Theoretical problem about traveler salesman

The problem doesn't get much easier when you know the exact length of the shortest path ahead of time. You can prove this by imagining you had a magic box (aka oracle) which could solve the problem if it was told ahead of time the exact length of the shortest path, and then use the magic box to solv...

- Mon Aug 31, 2015 6:20 pm UTC
- Forum: Serious Business
- Topic: Ethics of AdBlock
- Replies:
**639** - Views:
**125302**

### Re: Ethics of AdBlock

If so, I would argue that not using AdBlock (or some equivalent) is unethical. Getting infected by malware doesn't just affect you, if your computer becomes part of a botnet. Malware protection exists, entirely independent of whether it also blocks ads. Trying to prove the ethics of removing all ad...

- Sat Aug 29, 2015 2:29 pm UTC
- Forum: Serious Business
- Topic: Ethics of AdBlock
- Replies:
**639** - Views:
**125302**

### Re: Ethics of AdBlock

Would you call someone who chooses not to get a free flu shot during flu season unethical? What if you had a friend who was paid ten dollars every time he infected someone with the flu, and chose to support him by letting him infect you with the flu - would that be unethical? If so, I would argue th...

- Sat Jul 25, 2015 3:26 am UTC
- Forum: General
- Topic: Thoughts for ships
- Replies:
**90089** - Views:
**8463898**

### Re: Inspirations

Recently discovered that it's surprisingly difficult to exchange dollar bills for quarters.

- Tue Jul 14, 2015 2:33 pm UTC
- Forum: General
- Topic: What would a god have to do to convince you it's a god.
- Replies:
**41** - Views:
**10539**

### Re: What would a god have to do to convince you it's a god.

Permanently grant me immortality How exactly do you test this one? Yeah, so if anybody comes up to you and tells you they are a god, that's the first one you want them to tell you they just granted? Good luck with that. Claiming to believe that they were indeed a god after surviving a thousand year...

- Tue Jul 14, 2015 4:19 am UTC
- Forum: General
- Topic: What would a god have to do to convince you it's a god.
- Replies:
**41** - Views:
**10539**

### Re: What would a god have to do to convince you it's a god.

Permanently grant me immortality, the ability to teleport, the ability to shapeshift, the ability to travel to alternate universes, and the ability to kill a god. I would consider that sufficient proof of godhood.

Three out of five abilities would get at least a "maybe" out of me.

Three out of five abilities would get at least a "maybe" out of me.

- Sun Jun 21, 2015 10:53 pm UTC
- Forum: Coding
- Topic: Happy bases
- Replies:
**12** - Views:
**3443**

### Re: Happy bases

This might help: ... b^2+1 can be written as the sum of a square and an odd square in a nontrivial way if and only if it is composite. Could you explain that a bit more? I just came down with a major fever and can't really think straight, but here goes. The key fact is that the Gaussian integers - ...

- Thu Jun 18, 2015 8:00 am UTC
- Forum: Coding
- Topic: Happy bases
- Replies:
**12** - Views:
**3443**

### Re: Happy bases

This might help: there is a number n bigger than 1 with happy(n) = n in base b if and only if b^2+1 is composite. Proof: write n = bx+y with 0 <= x,y < b, then we are trying to solve the equation bx+y = x^2 + y^2. Multiplying by 4 and rearranging, this is equivalent to b^2+1 = (b-2x)^2 + (2y-1)^2, a...

- Sun May 31, 2015 11:03 pm UTC
- Forum: Coding
- Topic: Useful applications of recursion?
- Replies:
**19** - Views:
**5068**

### Re: Useful applications of recursion?

Topological sort on a directed acyclic graph. Also, finding articulation points in a graph.

The incredibly clever linear time find-the-median algorithm.

Finding a winning strategy in a two-player game.

The hashlife algorithm, Fast Fourier Transform, Strassen's matrix multiplication algorithm, ...

The incredibly clever linear time find-the-median algorithm.

Finding a winning strategy in a two-player game.

The hashlife algorithm, Fast Fourier Transform, Strassen's matrix multiplication algorithm, ...

- Sun May 31, 2015 8:37 pm UTC
- Forum: Logic Puzzles
- Topic: What number pen ??
- Replies:
**9** - Views:
**3292**

### Re: What number pen ??

Augh

**Spoiler:**

- Wed May 27, 2015 6:46 am UTC
- Forum: Serious Business
- Topic: Open-ended Moral Dilemma
- Replies:
**6** - Views:
**5971**

### Re: Open-ended Moral Dilemma

I'm going to assume that there is a door somewhere on the rooftop, but it has been locked to prevent us from simply leaving (I think most buildings have some sort of door to the roof?). Ask the girl to chew the gum, explaining to her that you think there is a chance it could trigger a sneeze which c...

- Thu May 14, 2015 3:57 am UTC
- Forum: Mathematics
- Topic: A maths joke I don't get
- Replies:
**8** - Views:
**9108**

### Re: A maths joke I don't get

There's also the trivial answer: 0. It's the differential operator that takes any function as input, and returns the (constant) 0 function as output.

Alternative answer: maybe by fg, your lecturer meant f∘g. Since (f∘g)(x) = c for all x, d/dx kills it. (So does 0, of course.)

Alternative answer: maybe by fg, your lecturer meant f∘g. Since (f∘g)(x) = c for all x, d/dx kills it. (So does 0, of course.)

- Sun May 10, 2015 11:37 pm UTC
- Forum: Mathematics
- Topic: Topology terminology question
- Replies:
**22** - Views:
**3414**

### Re: Topology terminology question

Back to the original question: do geodesics tend to eventually come back to their starting points? If a Riemannian manifold is compact, then so is its unit tangent bundle (the unit tangent space at any point is a sphere). By Liouville's theorem, the geodesic flow preserves some natural measure (call...

- Sun May 10, 2015 1:24 am UTC
- Forum: Mathematics
- Topic: Topology terminology question
- Replies:
**22** - Views:
**3414**

### Re: Topology terminology question

Sorry, let me ask the questions a different way - I'm probably asking in a silly way. 1) "What do a sphere, a torus, and a Klein bottle all have in common (but a plane doesn't)?" 2) "What do those things, a bounded region, and a manifold with a bounded metric all have in common?"...

- Wed May 06, 2015 1:13 am UTC
- Forum: Mathematics
- Topic: A maths joke I don't get
- Replies:
**8** - Views:
**9108**

### Re: A maths joke I don't get

(d/dx - 1) kills it, and doesn't rely on silly conventions like the d/dy answer (not everybody calls the output of a function "y", and for all we know x might be a function of y).

- Tue May 05, 2015 10:03 am UTC
- Forum: Serious Business
- Topic: Orthodox Judaism & Sexism [Title Change]
- Replies:
**233** - Views:
**53505**

### Re: How can I express logical arguments?

'Supreme Court of Israel' I'm not sure I understand this and once again it is important and needs to be explained, I assumed the church leaders in this case filled the role and that generally the community as a whole should be charged with dealing the punishment in the same way re:*stoning*and the ...

- Sat May 02, 2015 12:06 am UTC
- Forum: Mathematics
- Topic: Equations Like f(2x)=4f(x)
- Replies:
**8** - Views:
**5043**

### Re: Equations Like f(2x)=4f(x)

These sorts of equations are called functional equations. They come up often on math competitions (they are the most fun type of competition problem, in my opinion). One of my friends might have coauthered a book about them.