Wikipedia:Reference desk/Archives/Mathematics/2006 September 5

< September 4	Mathematics desk archive	September 6 >

Humanities Science Mathematics Computing/IT Language Miscellaneous Archives

The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions at one of the pages linked to above.

< August September October >

September 5

Polynomial Time

How do you prove that something can't be solved in polynomial time? Black Carrot 00:54, 5 September 2006 (UTC)

With great difficulty, especially if it turns out P = NP. However, you can usually determine if a particular algorithm for solving is non-polynomial by demonstrating how many times it has to loop. Proving there's no polynomial-time algorithm is generally much harder. Confusing Manifestation 01:30, 5 September 2006 (UTC)

The standard approach to proving that some problem P is hard, is to take a known hard problem H, and show that, you could (efficiently) transform any instance of H into an instance of P. Therefore, if you have an algorithm to solve P, you have an algorithm to solve H. If we know that there is no algorithm to solve H efficiently, then there can't be a way to solve P efficiently. There are some subtleties I've avoided here, mostly relating to the properties of the transformation procedure, but that's the basic idea.

However, in practice, there are a very large class of problems - the NP-complete problems - which are strongly suspected to be difficult, but we can't prove that they are difficult. So, it's very common to use reduction to show that a new type of problem is NP-complete. This gives an ever-expanding pile of problems which have this annoying property of probably being fundamentally difficult to solve, but that we can't prove that formally. --Robert Merkel

So, 1)It's very difficult to prove there's no such solution, 2)It's generally easy to prove that a specific solution won't work, 3)It's possible to prove that something can't be done if something else can't be done... yet 4)There exist problems for which this has been proven. I need something more specific to work with. Does anyone have an example of one that's been proven? Black Carrot 01:59, 5 September 2006 (UTC)

Sure, the halting problem is undecidable (can't be solved in general, given any amount of time), so any method that could be used to solve the halting problem is also undecidable. --Robert Merkel 02:38, 5 September 2006 (UTC)

And hence "does this program halt in exponential time" requries exponential time to test. Rich Farmbrough, 14:09 5 September 2006 (GMT).

There are some problems which have been proved to require an exponential amount of time. For example, see some refs in this paper: [1]. I've seen it in textbooks too but right now I don't recall where. --McKay 03:39, 5 September 2006 (UTC)

Also some problems require can in some case have an answer longer then any polynomial of the input length which surely implies you need so many steps. – b_jonas 21:18, 5 September 2006 (UTC)

To prove that a problem is NP, the easiest way is to show how a known NP problem can be solved using it (mapping the question into the known problem). Since the proof of that NP problem is already established, and you have just proven that this problem is at least as hard (a hard problem cannot be solved by an easier one), you have proven that it is also NP. There are lots of NP problems out there (e.g. subset sum). Undecideable problems like the halting problem aren't likely going to be of help, it is usually better to start with a problem that is similar to the one you already have. - Rainwarrior 07:39, 6 September 2006 (UTC)

Yes, but Rainwarrior, that's not what our friend asked. He wanted to prove that something can't be done in polynomial time. Merely proving that something is NP-hard establishes that we "don't know" of a method to solve it in polynomial time (and very strongly suspect that there isn't one). It doesn't prove that it's impossible. There is a very big difference between "we suspect" and "we know" in mathematics... --Robert Merkel 07:56, 6 September 2006 (UTC)

Yes. That question had already been answered, and I was answering a different question. Proving whether something belongs in NP is quite a practical thing to do (more practical, in general, than musing about how NP isn't proven), and I thought I'd answer that particular question just in case he meant that one. - Rainwarrior 19:54, 6 September 2006 (UTC)

I'll see if I can clarify. I'm not asking whether it can be proven impossible, conditional on something we don't know. I'm not asking whether something we can't do period, we therefore can't do fast, but good catch. I'm not asking whether something with such a huge output we can't even read it that fast, therefore can't be output that fast, but again, a valid exception. What I'm asking is very simple, and I think, a pretty reasonable question to want a straight answer to. I've heard that there are some problems that can be solved, for which it has been proven that they cannot be solved in polynomial time, ever. If such a thing has been done, how? Because really, I can't imagine it. McKay - If you can explain those to me, I'd appreciate it. Farmbrough - That sounds promising. Black Carrot 20:04, 9 September 2006 (UTC)

Farmbrough - Regarding "'does this program halt in exponential time' requries exponential time to test": I've been thinking about it, and I'm not sure that's how it would work. Even once a particular algorithm halted, that would give no answer to the general speed of that class of problems - any particular finishing time or set of finishing times could be nothing but luck, and even if you knew they were representative, they could as easily be a slow polynomial as an exponential or conversely, an unusually fast exponential vs a normal polynomial. Right? Black Carrot 05:21, 10 September 2006 (UTC)

If a problem can be shown to be equivalent to an EXPTIME-complete problem, then it is shown to be outside the class of things that can be solved in polynomial time. Classic examples of EXPTIME-complete problems (from the article) are "deterministic Turing maching accepts an input in at most k steps", "completely evaluate a position in generalized (arbitrarily large boards) Chess/Checkers/Go", "adapting an algorithm that acts on a graph in a "natural form" (e.g. an adjacency matrix) to instead act on a "succinct circuit" which is an exponentially smaller representation of the same input". I recall reading in the late 80s/early 90s that the semigroup factorization problem was EXPTIME-complete, but I have no reference at all for this. -- Fuzzyeric 03:48, 12 September 2006 (UTC)

n log n problem

Is there a "proper" method for solving the equation $nlog_{2}n=100$ for $n$? --Kainaw ^(talk) 14:38, 5 September 2006 (UTC)

Not as an analytical expression with elementary functions, but it can be expressed in closed form using Lambert's W function. The equation $n~\log _{2}~n=K$ can be rewritten to $n~\log ~n=K~\log ~2$, or $n^{n}=\exp(K~\log ~2)$. Using the formula provided in the article, the solution is then:

$n=K~\log ~2/W(K~\log ~2)$.

--Lambiam^Talk 16:22, 5 September 2006 (UTC)

I think we need a FAQ with Lambert W in it... Fredrik Johansson 16:32, 5 September 2006 (UTC)

What we need is a tutorial on how to use Lamber't W function to effectively solve maths problem. They sure didn't teach me this in high school. Ohanian 23:10, 5 September 2006 (UTC)

Teaching Maths

Can you direct me to a good bank of online teaching resources CD143.239.68.22 16:53, 5 September 2006 (UTC)

Online teaching resources, or CDs?

bbc.co.uk has good stuff inc lesson plans, online tasks etc. teachernet has lesson plans, as does part of yahoo (but it's quite big and I can't remember which part exactly). What topic, age group, ability etc? Rentwa 18:57, 5 September 2006 (UTC)

Just came across this link list (while searching for Lambiam's journal article.)EricR 19:18, 5 September 2006 (UTC)

Please look up this link. Happy to exchange. I need Latex source files in vector analysis, Fourier analysis, elementary probability and stats in order to save my time otherwise I have to do it myself VERY SOON in order to make my living. Please remove me (no hard feeling from me) if I have broken the rules of self-advertising although I have absolutely no intention to make any money from you. Just to promote international cooperation as educated and told by (IIE-1966). Twma 00:14, 6 September 2006 (UTC)

Seems OK as long as promotion does not become more explicit, although I'm not an expert on policy. You could add some (non commercial) text to your userpage or red username may suggest a fly-by-night spammer to some. Rentwa 09:17, 6 September 2006 (UTC)

Do not understand your last sentence. Please elaborate. Thank you in advance.

Just straight swaps with Latex source files to Latex source files. I just want to make life easier for myself by borrowing the others' teaching material. No commercial deal and no money involved. Acceptable?? Twma 00:58, 7 September 2006 (UTC)

You could add some text saying 'Hello, I'm...' etc to your userpage, then people might find you more approachable and swap more stuff with you. Your username looks red till you do, which is the same as someone who registered 5 mins ago to put linkspam on articles, that's all.

I begin to be aware that I MIGHT have a userpage with wikipedia. If this is what you mean, please tell me where can I find it. If your userpage means my web-page in Australia, please confirm. Why my name is RED and yours is blue? How do I change it into blue? I followed instructions to type in four ~ at the end. Then the DEFAULT is red for me and blue for you!! Thank you in advance.Twma 08:02, 7 September 2006 (UTC)

Just click on the link in red Twma which takes you to a page titled "Editing User:Twma" - just edit this, and it will become your userpage :-) Madmath789 08:05, 7 September 2006 (UTC)

Thank you. My name is in blue now. So I become a member of this extended family. Twma 09:00, 7 September 2006 (UTC)

Hello brother :) . Or is it sister? Welocome to wikipedia. I don't have any experience teaching in the fields you're interested in, but dozens if not hundreds of Wikipedians will. I will post some links on your talk page which is the tab immediately to the right of the one that says 'user page' and is marked 'discussion' :) . Rentwa 15:13, 7 September 2006 (UTC)

Educated and told by (IIE-1966), I am an old man. I am trying to understand what is MY TALK PAGE. It is very likely that people will get mad with me because I do not respond to their questions immeditately. I only come back to Wiki once or twice a week on the average. Twma 02:51, 8 September 2006 (UTC)

I'm sure it's acceptable, but I'm not an authority. :) Rentwa 05:59, 7 September 2006 (UTC)

Assuming you're offering straight swaps, that is. If you're just selling lesson plans then probably not. If it's the former, why not add some details to your user page and maybe you'll meet up with some other maths teachers. You might even be able to improve some of our articles. :) Rentwa 13:02, 6 September 2006 (UTC)

Subsets

If I have a set with 5 elements, it will have 32 subsets. I'm looking for a shortcut that can tell me the number of subsets with at least 3 elements, without having to write out all the possible subsets. Thanks for any help. --MZMcBride 19:49, 5 September 2006 (UTC)

Is this homework? How about a hint? Figure out how many subsets have 2 or fewer elements, and subtract from 32. --Trovatore 19:51, 5 September 2006 (UTC)

It's not homework (I promise). I just can't seem to find anything on the web for a formula that would make this easier. What if there were 6 or 7 elements? It would be too cumbersome to subtract the subsets. --MZMcBride 20:07, 5 September 2006 (UTC)

This is basic combinatorics. Specifically, with a set of n elements, the number of subsets with exactly k elements is given by the binomial coefficient ${n \choose k}={\frac {n!}{k!(n-k)!}}$. —Ilmari Karonen (talk) 20:20, 5 September 2006 (UTC)

You may want to look at Power set. – b_jonas 21:15, 5 September 2006 (UTC)

Thanks for the quick responses. --MZMcBride 01:20, 6 September 2006 (UTC)

History of logarithms

I've seen the claim on a few websites that tables of logarithms were made by medieval Muslim mathematicians, but someone removed that statement from the history section of the logarithm article as being Islamist propaganda, or something. I'm not the one who inserted it in the first place, but I'd be happy to reinsert it, with a citation, if I can find one. Does anybody know of a good reliable source confirming that Muslims were making log tables in the 13th or 14th century? -GTBacchus^(talk) 22:48, 5 September 2006 (UTC)

It's propaganda. Coming up with the idea or concept of logarithm is different from creating log tables and using them. They confused one with the other. Ohanian 22:59, 5 September 2006 (UTC)

And the edit in question says that the Muslim mathematicians created log tables. Is that false? Is it irrelevant to the history of logarithms? -GTBacchus^(talk) 23:01, 5 September 2006 (UTC)

My sources claim "In 1614, Napier published his table of logarithms." "The Scottish mathematician John Napier spent years working out the formulas that would give him appropriate exponents for a great many numbers." Cite: Asimov's Chronology of Science and Discovery - Isaac Asimov

Of course, the concept of logarithms is not hard to derive, even for an elementary mathematician, so it is possible that Muslims used log tables, but this is my best source, and I would try to stick with verifiable sources if you can. M.manary 23:04, 5 September 2006 (UTC)

Oh, don't worry, that's why I specifically asked for a reliable source confirming that Muslim mathematicians produced tables of logs. I'm not going to add anything without a verifiable source, or I wouldn't be bothering to ask for one. -GTBacchus^(talk) 23:08, 5 September 2006 (UTC)