Wikipedia:Reference desk/Archives/Mathematics/2011 December 7

Welcome to the Wikipedia Mathematics Reference Desk 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 on one of the current reference desk pages.

December 7

3SAT Question

Hi. What is the best worst case complexity for 3SAT (that sounds weird...) I'm curious since I've got it down to O(2 ** (N/3)), and I'm wondering how much better it can be made. Thanks in advance:-) * N being the number of variables not literals. From what I can find, the best as of 2008 is around 1.4 something. This is around 1.25ish; is that worth doing something with or just trivia?209.252.235.206 (talk) 11:34, 7 December 2011 (UTC)

The goal is to get it down to O(n). That means that the n cannot be an exponent - which really means that the entire approach that is usually taken needs to be changed. The common mistake is to attack it with something like "suppose I have a machine with n switches on it..." The solution must be fixed, not an expanding thing that grows to the problem size. I've already received at least 100 solutions that go: Given n variables, get a computer with nxn registers. Hardcode memory so all the combinations of 0 and 1 are in it. Then, in O(n) look for a solution that comes out true. -- kainaw™ 13:53, 7 December 2011 (UTC)

I may be confused, so I apologize if so. But here are three things;

1.) Are you talking about/think I'm talking about solving P=NP? If so, wouldn't you mean O(n ** a)? I don't think anybody expects a linear time solution to 3sat.

2.) While P=NP is very interesting, I understand that there is some interest in algorithms for NPC problems that run in O(a ** n) for small a, I just don't know how much or how far its come. That's what my question is about.

3.) I don't understand what you mean about hard coding and the solution being fixed or about receiving 100 solutions that go a certain way. could you please elaborate, I feel as if I am missing something substantial here. 71.195.84.120 (talk) 15:20, 7 December 2011 (UTC)

I mentions O(n) as a goal - albeit an impossible one. You asked if was just trivia and, that was my attempt at an answer. Removing n from the exponent would certainly be more than trivia. You nailed why - it would get into proving P=NP. As for the hard-coded solution, that comes from many students not truly understanding P and NP. The entire solution is the solution. So, if step 1 is something like "get n Turing machines", then getting n Turing machines is part of the solution - which could be impossible for very large values of n. Students tend to think that getting a bigger machine for bigger problems is allowed. Then, I can do a 3SAT quickly. Step 1, get a huge machine that can calculate the given 3SAT in one step. Step 2, press start. I know that isn't your suggested solution, but that is a solution I receive (often multiple times) every semester. -- kainaw™ 18:44, 7 December 2011 (UTC)

Just squeezing in this as an example of someone claiming to solve 3SAT by using an expandable solution. You can see from the geek comments that it isn't a new, novel, or correct solution. -- kainaw™ 19:17, 7 December 2011 (UTC)

I think I understand the point you are making, I just don't understand how it relates to what I'm asking. Essentially, I can solve 3SAT in O(1.25 ** n), the best I've seen is O(1,45 ** n). Is this worth caring about or just some random trivia? As pertains to this question, I have no interest in P=NP and the such, and am not talking about removing the exponent. Thank you for your replies:-) 71.195.84.120 (talk) 18:52, 7 December 2011 (UTC)

I don't know the field very well, but if truly no one has done that before, then I bet it's publishable. Don't pass up a paper just because it might not be revolutionary. --Trovatore (talk) 19:10, 7 December 2011 (UTC)

That, actually, brings me to another question. I study recursion theory and set theory for fun, usually at work. I've read a good deal of research level papers, text books, etc. However, my extent with math writing is confined to my personal notebooks; further, I don't have any type of degree and am not in school. So, while I can do math (at least at a graduate level), I have no clue how to go about publishing. Do you know of any information/resources I could look at that would help me to be better able to do this? On a side note, I really hope this doesn't make me come off as a crank. 209.252.235.206 (talk) 05:46, 8 December 2011 (UTC)

Well, it's not easy. Most people who publish are currently associated with a university. I know one guy who did some very nice work while not at a university, and used it to get back in to academics (normally very unlikely, but this guy is good), but he did have a degree, and knew people who knew he was good.

Under the best of circumstances, evaluating mathematical work is difficult and takes a lot of time. So if editors are unwilling to really seriously consider submissions from someone that no one knows, it doesn't make them evil and doesn't mean that they're trying to keep high barriers to entry; it's just a cold cost-benefit analysis.

That doesn't mean you shouldn't try! I just am not quite sure how you get your foot in the door. Do you know anyone in the field personally? --Trovatore (talk) 07:37, 8 December 2011 (UTC)

No, unfortunately. For the most part, I have no formal academic experience past highschool and lack any personal contacts. All of the books I read are either on my computer or physical books I've purchased (I have a very extensive personal library), so I don't even frequent areas where I might encounter anyone in the math community. To be honest, I really love mathematics and find it fascinating; but I've never had the opportunity to pursue it in a nonpersonal context. Sadly, this seems to be hindering my ability to do anything with what I've worked on (In a larger context; not that I'm assuming there is anything worth doing with it:-)) However, I can definitely understand the reticence to spend time on material from an unknown person, looking around the internet, I'm sure math/science journals get flooded with unusable material and I would imagine it takes a while to actually review any given paper.209.252.235.206 (talk) 08:27, 8 December 2011 (UTC)

I wouldn't be surprised if an algorithmics journal might take a look at your 3SAT solver, if the argument is straightforward and clearly expressed (and correct, of course). The only one I know the name of is Algorithmica but I'd speculate that there are lots of them. If you can show that you can do correct and nontrivial work that way, maybe people would be more likely to be interested in your other stuff too. Failing that there's always the arXiv, which is publication in a sense, but gets back to the problem of how you get someone to actually read it. --Trovatore (talk) 18:10, 8 December 2011 (UTC)

I will definitely take a look at publishing that way; thank you very much for your help:-)I would love to one day be able to share something useful with others (again, not assuming, I have any such thing) For some reason, I never really considered any of this until recently, I've always just seen math as something I did for enjoyment; it kind of makes me wish I had gotten a degree of some sort. Again, thank you for all of your help:-) Phoenixia1177 (talk) 10:46, 9 December 2011 (UTC)

Three-dimensional continuous chaotic system with an exact solution

I would like to experiment with chaotic maps, but I would prefer a system whose x, y, and z values can be determined given t (i.e., $x(t)$, $y(t)$, and $z(t)$). I have asked a similar question before, but I have not found what I am looking for. The system doesn't have to come from a natural process. Can anyone detail such a system for me? --Melab±1 ☎ 17:28, 7 December 2011 (UTC)

I assume the answer is no. Noone can detail such a system for you. Chaotic systems are characterized by not being predictable. Bo Jacoby (talk) 20:08, 7 December 2011 (UTC).

I don't think the existence of such a system can be ruled out so easily. Such a system may not exist, but this is not due to "unpredictability" of a chaotic system. That is, I believe that a large positive lyapunov exponent does not preclude analytic solutions. For instance, this paper [1] describes how exact analytic solutions to a chaotic oscillator can be used to set up secure a communication channel. (I may be missing something; it's been a while since I've studied this kind of thing in detail.) SemanticMantis (talk) 21:06, 7 December 2011 (UTC)

Oooooh, nice find, SemanticMantis! Melab-1, I seem to remember that the last time you asked (I can't find it), somebody gave an example of (I think) a 1D chaotic map that can be solved exactly. You could extend this to 3 dimensions by adding two extra variables that behave in any way you like - or maybe you would see that as cheating? 130.88.0.69 (talk) 22:50, 7 December 2011 (UTC)

I was the one who found it on MathWorld. The one-dimensional chaotic map you are thinking of is the logistic map—$x_{n+1}=r\cdot x_{n}\cdot (1-x_{n})$—which is a discrete chaotic map. $x_{n}$ has a closed-form solution when $r=-2$, $r=2$, $r=4$. --Melab±1 ☎ 00:02, 8 December 2011 (UTC)

I was obviously completely mistaken. But why not pick a simpler example? Consider a real frequency ν and the complex phase factor a=e^2πiν and the sequence aⁿ for integer values of n. If ν is rational, then the sequence is periodic, otherwise it is chaotic. Any tiny imprecision in ν is amplified until eventually the phase nν mod 1 is unpredictable. Bo Jacoby (talk) 07:29, 8 December 2011 (UTC).

I didn't know that one. I cannot use a one-dimensional system because those are discrete. --Melab±1 ☎ 22:26, 8 December 2011 (UTC)

Uh? You can set $x(t)=sin(\nu t)$ -- one-dimensional and fully continuous. Define $y(t)$ and $z(t)$ similarly if you want more dimensions. The problem with this (and Bo's) idea is that the Lyapunov exponent is 0, which is not very chaotic. 98.248.42.252 (talk) 15:47, 9 December 2011 (UTC)

That is why I need something that can be truly be called "chaotic". --Melab±1 ☎ 18:30, 10 December 2011 (UTC)

Doesn't my simple example satisfy the conditions mentioned in the article on Chaos theory? Bo Jacoby (talk) 21:57, 10 December 2011 (UTC).

I guess it might, but I am under the impression such a function may need to be a little more complicated. I would also like to see one that generates patterns like Lorenz attractor and uses no irrational numbers. --Melab±1 ☎ 22:37, 10 December 2011 (UTC)

I don't think that the function itself feels any need to be complicated. Perhaps you feel a need for the function to be complicated. Why is is so? Bo Jacoby (talk) 07:30, 13 December 2011 (UTC).