PDA

View Full Version : STEM thread part II


The Unreasoner
12-14-2015, 06:43 PM
So I will get around to PSPACE again, but first I had a physics question:

Everyone says 'spooky action at a distance' can't send information faster than light, but surely you can probabalistically? If we have 3 pairs of entangled bits separated by a light year and a prearranged time of transmission (and suitably synchronized clocks), couldn't I (the sender) measure the three bits vertically to send a one, and horizontally to send a zero? Then the receiver could measure them all vertically, and get the bit with only a one in eight chance of a false positive (and no chance of false negative). You could even scale up, and get the .125 down below an arbitrary theshhold.

The Unreasoner
12-15-2015, 12:11 AM
So I just remembered that the outcome is still randomly spin up or down. Though part of me still thinks that there must be some way to send imperfect info faster than light (when I was in HS, I didn't know gravity waves weren't instantaneous, and came up with a proof of concept project using vast chunks of antimatter to annihilate portions of distant stars, and thought I was a genius. Unfortunately, my teacher didn't know either, and couldn't correct me.


So back to Boolean formulas. Anyone who followed my last thread probably noticed how innaccesible/dull I made the tattoo flowchart after repeated 'reductions'. And some of you (Kimon) may rightly be asking yourselves, 'why should I give a shit?'

This really comes down to languages and logic. The most important question facing humanity (far greater in importance than things like stopping the environmental crises, fusion power, or how to beat ISIS (my plan? Send a token force to Dabiq, and don't turn into salt)) is: does P equal NP? The reason is this: any problem that we can check a given answer for with a Turing Machine (iow a computer, but specifically the kind we have now) quickly is part of the complexity class NP. When that same machine can actually find an answer quickly, it's in P. If they are (though it's generally believed they are not) equal (and we know how, ie no diagonalization nonconstructive bullshit), the world changes drastically. Mostly for the better/best. There are people that whine about it destroying creativity, that anyone who could recognize good art would become an artist, but it's easy enough to at least probabalistically disprove that. Though you could write 'Bach' music with a computer, in the sense that a computer couldn't tell the difference.

But what other sorts of problems can be checked quickly? Quite a few, actually. Physics, genetics, biology, chemistry, medicine would advance at (quite literally) an exponential rate, given a method to solve NP problems quickly. Cancer? Cured. Fusion? Done. Controlled mutation? Well, how many penises do you want? AI would advance to Sci-fi levels, hunan languages could be translated perfectly. Efficiency in everything. Perfect efficiency. GM yeast with DNA computers in your bloodstream that mutate as needed to produce needed meds or proteins. Maybe we'll even find a way to safely modulate our inactive genes in a way that lets us store a record of our history and knowledge, so that it could survive as long as we do. Even mathematics (real mathematics) could be partially automated.

And there is no (or almost no) exaggeration in any of that. We wouldn't need aliens or God to teach us all of the mysteries of the universe anymore. We would have the power to unlock almost any knowable one ourselves. Although I suppose God would still be technically responsible, assuming we got our mathematical abilities from him. Or maybe the aliens will be the ones to give us this Nondeterministic Oracle.

In any case, this is why I showed the reductions in the last thread. Because this means that all of these problems are essentially the same problem, and they will either stand or fall together. If just one has a chink in its armor, the first person to break through it will have all of the power of a living Oracle. This is not hyperbole.

But then, most experts feel that P is not equal to NP, so we'll need to tackle these problems one at a time, with heuristics, cunning, and a bit of luck.

Nazbaque
12-15-2015, 01:28 AM
It would still require for us to know what questions to ask and how to ask them. That is the fundamental problem. How to turn any given problem into mathematics. That's basically the difference between truly understanding art and being an advanced appreciator of it. Most artists in the whole human history didn't belong to the former. In the absolute terms this requires, most artists had simply reduced the field of their wild guess but still lacked the true understanding. Human perception is at the moment incapable of fullfilling this end of the bargain.

The Unreasoner
12-15-2015, 01:28 AM
And on that note, we'll take another look at Boolean statements. As it happens, almost any type of problem can be encoded in such a statement. You'll recall that it takes several variables, assembled in clauses, with the operators AND, OR, and NOT. The structure of the problem is embedded in the contents and format of the statement's clauses. Something like (x1 v x2 v x3) ^ (x1 v x2 v x3). quick recap, I use 'v' as OR, '^' as AND. '' is NOT. Variables are either TRUE or FALSE, and the entire statement produces a single output (also TRUE or FALSE). The thing of interest isn't evaluating the function for a specific input. This is mostly straightforward, and is done quickly. As I've said, the checking the correctness of a specific answer is fast for all problems in complexity class NP. The hard part is finding them.

Some functions are easy to invert (iow, find the input(s) given an output). For instance, f(x)=x^2. If you know the output is 4, x is either 2 or -2. Even some functions with multiple variables are easily inverted. f(x,y)=x+y has a set of points as its possible inputs for any given output (in this case, the line with slope -1 and y intercept at the output). But Boolean functions are a bit trickier to work with. The variables are binary, the operators are strange, and there can be nested groups with convoluted grammar.

So how do we manipulate them? There are tools from Boolean algebra that allow us to toy with the statement; to get rid of or add nesting, to insert or remove variables from a clause. It has its own distributive property and identities. This is how I (or, more accurately, Wolfram Alpha) took the original convoluted statement with layered nesting that was derived from that tattoo flowchart and into a standardized form (specifically, Conjunctive Normal Form). While CNF may mask or distort underlying structure in a more exotic statement, it does allow for certain solving methods and reductions. One of which I will cover now.

CNF is essentially an AND list of OR lists. But Disjunctive Normal Form is practically a list of the solutions (inputs). It's an OR list of AND lists (and any AND list in it that doesn't contradict itself is a solution). So how do you get this magical DNF?

There's a proper way, but I'll show you a simpler one I usually used that may be more familiar. It also eliminates self-contradictions as you go. I call it Boolean arithmetic.

It's almost the same as the arithmetic you know, except:

Only zeroes and ones exist. One consequence of this is that any number (even if it's a variable) multiplied by itself remains unchanged. Therefore a^2*b^3*c^7 is just abc.

Addition is different. While a number plus zero remains unchanged, so does a number added to itself. This means coefficients are discarded. 5a is just a.

Every variable has a negation variable (denoted here as a'). A variable added to its negation is 1, a variable multiplied by its negation is 0.


So to recap:
0+0=0
0+1=1
1+1=1
x+0=x
x+1=1
x'+0=x'
x'+1=1
x'+x=1
x'*x=0

So, how do we use this on the example above (and repeated below)?

(x1 v x2 v x3) ^ (x1 v x2 v x3)

Replace the negated variables with the negation variables, the AND operators with *, and the OR operators with + (I'll also switch to a b and c):

(a'+b+c)*(a+b'+c)

then distribute normally, but applying the modified rules above.

So we get:
a'a+a'b'+a'c
+
ab+b'b+bc
+
ac+b'c+cc

Then:
0+a'b'+a'c+ab+0+bc+ac+b'c+c

Since c is by itself, you can quickly group and factor terms that include it:

a'b'+ab+c*(a'+a+b'+b)
a'b'+ab+c*(1+1)
a'b'+ab+c*(1)

Finally:

a'b'+ab+c

Each term represents a suitable input: (F,F,NA; T,T,NA; NA,NA,T)

Next we'll try it on something more complicated.

The Unreasoner
12-15-2015, 01:30 AM
It would still require for us to know what questions to ask and how to ask them. That is the fundamental problem. How to turn any given problem into mathematics. That's basically the difference between truly understanding art and being an advanced appreciator of it. Most artists in the whole human history didn't belong to the former. In the absolute terms this requires, most artists had simply reduced the field of their wild guess but still lacked the true understanding. Human perception is at the moment incapable of fullfilling this end of the bargain.

Exactly. The art of asking good questions is humanity's highest. It takes a great mind to use great tools.

Nazbaque
12-15-2015, 01:52 AM
Exactly. The art of asking good questions is humanity's highest. It takes a great mind to use great tools.

Or a lucky guess.

GonzoTheGreat
12-15-2015, 04:02 AM
Some functions are easy to invert (iow, find the input(s) given an output). For instance, f(x)=x^2. If you know the output is 4, x is either 2 or -2. Even some functions with multiple variables are easily inverted. f(x,y)=x+y has a set of points as its possible inputs for any given output (in this case, the line with slope -1 and y intercept at the output). But Boolean functions are a bit trickier to work with. The variables are binary, the operators are strange, and there can be nested groups with convoluted grammar.
An additional problem (and actually a very fundamental one) is: how many variables are relevant in the function?
If you know that the answer is "4", that still doesn't tell you whether the question is the square of -2, the standard number of Beatles, or some weird Boolean combination thereof.

The Unreasoner
12-15-2015, 06:18 AM
An additional problem (and actually a very fundamental one) is: how many variables are relevant in the function?
If you know that the answer is "4", that still doesn't tell you whether the question is the square of -2, the standard number of Beatles, or some weird Boolean combination thereof.

I can't tell if you are making a joke, a subtle point, or asking a serious question.

You do, of course, need the definition of the function along with the output, or you're absolutely right. Inversion would be impossible. The relationships between variables varies wildly even among some standard functions. And if you could invert nonstandard functions easily, you could prove the Riemann Hypothesis. And the zeta function has only one variable.

Boolean sentences have many variables with often hidden or implied relationships. And they are fundamentally nonstandard (in college I found a way to convert an arbitrary sentence into a continuous, one parameter function, but to invert it you needed to evaluate a horrifying improper integral. I later found out that it was more or less just another cosine integral problem, and NPC in its own right).

Or maybe you were pointing out that PSPACE is different? In which case you are absolutely right, but I'm not quite there yet. But the teaser version: what if you ask me a (factual/logical) question, I give you the (or a) correct answer, but the answer is uncheckable for all intents and purposes? One example of such a problem comes from games: for reversi, go, checkers, or (generalized) chess on an infinite board, how do you even verify a (given) 'perfect move'? iow, I could tell you to place a stone in 3-5-9 in reversi, confident that whatever move your opponent plays next, a perfect, immutable, path to victory remains open to you. But how do you check that?

PSPACE is games where NP is puzzles (infinite sudoku is NP complete). It's SAT plus ontological operators (for all/there exists). It's a step beyond. But still an open problem. One that is closed is the one concerning hypercomputing. Hypercomputation needs an unbounded halting oracle. And considering the fact that perfect modelling of physical reality is believed to be Turing Complete, not likely physically possible.

Or maybe you think I dumbed everything down too much, and are just toying with me to point out you guys are not idiots, and I'm coming across as condescending. And if that's the case I apologize. This is already a self-selected niche thread. I don't need to teach arithmetic. I was shooting for middle ground, but I will consider the audience in the next round.

In the meantime, dors anyone understand these EM drives? I thought they were a hoax, but apparantly not.

GonzoTheGreat
12-15-2015, 06:31 AM
What I was aiming at is that being able to find such solutions would be very useful, but it doesn't help if your problem is figuring out what function is actually relevant. And that's basically what physics is all about: finding the rules that govern reality.

To show that problem for another field: consider curing cancer. You say that would be easy, with this extra mathematical method. Let's assume that this math trick had been available in the 19th century already, before anyone knew about genes, DNA and the like. Would it then really have been much use in finding a cure for cancer?
We now know a lot of reasons why it wouldn't be. But we don't know all about cancer, so there could still be unknown unknowns which would still prevent an easy solution, even if we could evaluate all the known parameters using this math trick.

The Unreasoner
12-15-2015, 03:39 PM
What I was aiming at is that being able to find such solutions would be very useful, but it doesn't help if your problem is figuring out what function is actually relevant. And that's basically what physics is all about: finding the rules that govern reality.

To show that problem for another field: consider curing cancer. You say that would be easy, with this extra mathematical method. Let's assume that this math trick had been available in the 19th century already, before anyone knew about genes, DNA and the like. Would it then really have been much use in finding a cure for cancer?
We now know a lot of reasons why it wouldn't be. But we don't know all about cancer, so there could still be unknown unknowns which would still prevent an easy solution, even if we could evaluate all the known parameters using this math trick.

Again, you are mostly right. I'm putting quite a bit of faith in the intelligence of the questioner.

But then, I think you underestimate the Oracle. While 19th century medicine couldn't exploit such an algorithm, modern medicine certainly can. For instance, cancer is already cured, from the mathematician's perspective. It's a matter of finding a protein chain that will fold into a structure that strangles cells with one genetic sequence while leaving another unharmed. Obviously you'd have a separate instance of the problem for every patient (or even the same patient with a slightly different cancer). It's not one size fits all, it's made to order. But the genetic knowledge, algorithms, and protein production capabilities we have today are enough. Only our software and hardware are lagging.

As for physics: if you tell it what you observed and which mathematical rules to obey, it will be able to find the smallest set of equations that perfectly explains all the data. And if that one doesn't work for whatever reason, it could find the second smallest. And so on.

The Unreasoner
12-15-2015, 03:56 PM
Now let's revisit tattoos using Boolean arithmetic.

From the old thread:

(PvovX)^(evfvX)^(kvlvX)^(kvmvX)^(Rvovq)^(DvXvY)^(G vXvY)^(NvXvY)^(avXvY)^(bvXvY)^(hvXvY)

A is always FALSE
B is always FALSE
C is redundant (can be either TRUE or FALSE without affecting the solution in any way)
D is always TRUE
E is TRUE iff z12 is not a member of the subset
F is TRUE iff z13 is not a member of the subset
G is always TRUE
H is always FALSE
I is redundant
J is redundant
K is TRUE iff z11 is not a member of the subset
L is TRUE iff z08 is not a member of the subset
M is TRUE iff z05 is not a member of the subset
N is always TRUE
O is TRUE iff z19 is not a member of the subset
P is TRUE iff z16 is a member of the subset
Q is TRUE iff z01 is not a member of the subset
R is TRUE iff z02 is a member of the subset

And the legend again:
A= Are you drunk?
B= Are your friends egging you on?
C= Are your friends laughing?
D= Does it have a special meaning?
E= Is it a name?
F= Is it the name of a significant other?
G= Is it unique?
H= Is it 'Steve-O' unique?
I= Are you trying to fit in?
J= Are you sure you are not trying to fit in?
K= Will it be visible when you are dressed?
L= Are you a white collar worker?
M= Will it be on your face?
N= Is it appropriate for children to see?
O= Is it going on the small of your back?
P= Do you want men to think you are easy?
Q= Are you a man?
R= Do you prefer to 'catch'?

The Unreasoner
12-15-2015, 04:21 PM
I'm on my phone, and plus signs are pain. So if it's all the same, we'll just use spaces and parentheses. Lower case letters are negation variables.

(PvovX)^(evfvX)^(kvlvX)^(kvmvX)^(Rvovq)^(DvXvY)^(G vXvY)^(NvXvY)^(avXvY)^(bvXvY)^(hvXvY)

(P o)(e f)(k l)(k m)(R o q)

That removed the known variables (if you like, you can treat them as a common factor for all the terms in the final set).

Next:
(PR Po Pq Ro o oq)(k kl km lm)(e f)

And that's actually it. Since no variable appears (or has its negation appear) in more than one clause, this is essentially DNF factored. If you choose one element from each of the three lists, it will work.

Returning the common factor:

(DGNabh)(PR Po Pq Ro o oq)(k kl km lm)(e f)

The Unreasoner
12-15-2015, 04:34 PM
You can count solutions/make the exhaustive list by reincluding the redundant variables.

(DGNabh)(PR Po Pq Ro o oq)(k kl km lm)(e f)(C c)(I i)(J j)

1*6*4*2*2*2*2=384. Which, you may note, is not 165 or whatever the other number was for the last thread. Clearly I fucked up somewhere, just don't know where.

ETA:
I forgot the list isn't exhaustive because some variables are conditionally redundant. Which may make at least one of my old answers right, though 384 is meaningless.

ETA:
Reinserting conditionally redundant variables into the ef clause raises it to three terms (everything but EF). The opqr clause goes to 11. And the klm goes to 5. So I was right about 165 after all. Now I just have to see if 8*165 equals my old guess.

The Unreasoner
12-16-2015, 05:28 PM
So let's build some functions. I think we'll look at chess pieces on a 4x4 board.

In all systems, you need some way of encoding information. We'll use 2 bits with an x tag to represent the column, and two with y to represent row.

00 (or FALSE, FALSE) is 1
01 is 2
10 is 3
11 is 4

So let's consider a function T(Rx1,Rx2,Ry1,Ry2,Hx1,Hx2,Hy1,Hy2), where T determines if a rook R threatens a piece H. We'll assume no other pieces are on the board. Essentially we need to check if H and R are in the same row or column (and if we wish, not both).

We'll do this with a function K, which checks whether two pairs of bits are the same.

Something like this:
K(a1,a2,b1,b2)=((a1 xor b1)v(a2 xor b2))

Now xor is just exlusive or, but in order to define everything in AND/OR/NOT gates, we'll say i xor j is Q(i,j)=(ivj)^(ivj).

And that's all we need. So T=Q(K(Rx1,Rx2,Hx1,Hx2),K(Ry1,Ry2,Hx1,Hx2)), and is TRUE iff rook R and piece H share either the same row or the same column, but not both.

Now let's turn it into CNF.

The Unreasoner
12-16-2015, 05:51 PM
First let's replace Rx1,Rx2,Ry1,Ry2,Hx1,Hx2,Hy1,Hy2 with a,b,c,d,e,f,g,h.

Then we have Q(K(a,b,e,f),K(c,d,g,h)).

Q((Q(a,e)vQ(b,f)),(Q(c,g)vQ(d,h)))

((((((ave)^(ave))v((bvf)^(bvf))))v((((cvg)^( cvg))v((dvh)^(dvh)))))^(((((ave)^(ave))v(( bvf)^(bvf))))v((((cvg)^(cvg))v((dvh)^(dvh) )))))

Now we just have to distribute and simplify. Though I think I'll just use Wolfram Alpha, because it's a pain to do by hand.

The Unreasoner
12-16-2015, 06:16 PM
Can anyone see what's wrong with this input? Wolfram Alpha isn't liking it.

BooleanConvert[(((! (((A || E) && (! A || ! E)) || ((B || F) && (! B || ! F)))) || (! (((C || G) && ( ! C || ! G)) || ((D || H) && (! D || ! H))))) && (! (! (((A || E) && (! A || ! E)) || (( B || F) && (! B || ! F)))) || ! (! (((C || G) && (! C || ! G)) || ((D || H) && (! D || ! H)))))),"CNF"]

GonzoTheGreat
12-17-2015, 04:09 AM
I've looked at it a bit, and the number and pairing of brackets seems all right. So that fairly obvious issue isn't it.

Then I tried feeding it to Wolfram Alpha myself, but that said the string was too long, cut of the end of it and then complained that it wasn't properly formatted. The latter was of course believable at that point, but not really helpful, since the problem was generated by WA itself.
In order to use the whole string I would need a paid version of WA, which I don't have. So I don't know what it says about the whole.
I did try to feed a (more or less randomly chosen) subset into WA, and that did not give any problems.

So I would advice you to try to chop it in half, and then feed each half separately into WA. If either half gives you the same problem back you have now, that will at least allow you to zoom in on what that problem is. Maybe you can then even solve it.

Daekyras
12-17-2015, 12:07 PM
I had a busy couple of days and I come back to find I missed this thread?

Damn!

I'll give it a close going over and stick in my penny's worth in a day or so. Damn!

The Unreasoner
12-17-2015, 07:53 PM
I've looked at it a bit, and the number and pairing of brackets seems all right. So that fairly obvious issue isn't it.

Then I tried feeding it to Wolfram Alpha myself, but that said the string was too long, cut of the end of it and then complained that it wasn't properly formatted. The latter was of course believable at that point, but not really helpful, since the problem was generated by WA itself.
In order to use the whole string I would need a paid version of WA, which I don't have. So I don't know what it says about the whole.
I did try to feed a (more or less randomly chosen) subset into WA, and that did not give any problems.

So I would advice you to try to chop it in half, and then feed each half separately into WA. If either half gives you the same problem back you have now, that will at least allow you to zoom in on what that problem is. Maybe you can then even solve it.

I thought it was probably brackets too, but couldn't see an issue with them. Put the first half in, didn't work. But the first and second quarters worked fine, so I'm guessing it's a length issue. Though it didn't cut it off or tell me.

On the bright side, it turns out WA does recognize xor, so I'll just feed it the Q equation version, which is much shorter.

ETA: So it could handle that version, but just gave me some Boolean Operator number or something like that. Maybe there's an index of small circuits it's referring to.

And, amusingly, it gave me the truth density of 3/8. Which works. But it's much easier to count the spaces on our chessboard and subtract the safe ones than whatever WA did.

The Unreasoner
12-18-2015, 04:40 PM
Probably more important than the conversion itself are the techniques used.

So on that note:
NOT travels inward until it attaches to a literal (variable). Functions flip:

NOT (A OR B) is (NOT A AND NOT B)
NOT (A AND B) is (NOT A OR NOT B)

Distributing across an AND:

A AND (B OR C) is (A AND B) OR (A AND C)

Distributing across an OR:

A OR (B AND C) is (A OR B) AND (A OR C)

Associative rules apply:

A AND(OR) (B AND(OR) C) is (A AND(OR) B) AND(OR) C


If you are taking it beyond CNF SAT to 3 SAT, you need a way to reduce the size of an OR clause. This is done by invoking a new variable:

(A OR B OR C OR D) is (A OR B OR X) AND (C OR D OR NOT X)

And nested clauses of the same function collapse to one level:

A AND(OR) (B AND(OR) (C AND(OR) D)) is A AND(OR) B AND(OR) C AND(OR) D

Next we'll look at circuits, then past attempts to prove P vs NP.

The Unreasoner
12-18-2015, 08:06 PM
Actually before we move on to circuits, I thought we'd cover two more things.

First: a way to test if two Boolean functions are essentially the same. This is useful if you are trying to find a more efficient formula (ie, fewer clauses or variables, less nesting, etc).

Function x is essentially equivalent (iow, equisatisfiable) to y if the function (x xor y) is always true. You can confirm this by converting to CNF and checking that each OR clause has both a variable and its negation.

Another thing I thought I'd poibt out is that there are only finitely many possible Boolean functions (that are fundamentally different) for any finite set of variables. This can be seen by noting that any equation can be written in CNF. We'll look at equations in three variables for the example.

The largest possible clause contains an instance of every variable, and there are two states for each variable. So there are 2^3 clauses of size 3.

Clauses of size 2 contain all but one variable. There are 3 possibilities for the excluded variable, and 2^2 possibilities for the rest.

Finally there are 3*2 possible clauses of size one.

This gives us a total of 26 possible clauses. The number of formulas is simply the number of possible subsets aside from the empty set. This number is 2^26 -1, or 67108863.

Almost 70 million formulas in three variables.

Now a question: there are only 8 possible inputs and two possible outputs. Why aren't there only 16 formulas? (Yes, I know the answer, and I will get to it.)

The Unreasoner
12-21-2015, 02:32 PM
Okay. Slight detour from the original topic in light of some new info.

Graph Isomorphism appears to now have a far superior algorithm. It also relates to our current topic. So I'll get to unpacking some of this.

Now on YouTube: HD video of first talk
Dates: Tue Nov 10, Thu Nov 12, Tue Nov 24, Tue Dec 1
University of Chicago
Combinatorics and Theoretical Computer Science seminar
Date: Tuesday, December 1, 2015
Time: 3:00pm
Place: Ryerson 251
Speaker: Lszl Babai (University of Chicago)
Title: Graph Isomorphism in Quasipolynomial Time III: The "Split-or-Johnson routine"
Abstract:
In this third talk of the series we present the details of the "Split-or-Johnson" routine, the second canonical partitioning algorithm required for the master algorithm. In the previous talk, the "Design Lemma," the first partitioning algorithm (reduction from k-ary to canonical binary relation) was presented. The talk can be understood without knowledge of the master algorithm outlined in the first talk. The Weisfeiler-Leman canonical refinement process discussed in the second talk will be briefly reviewed and extensively used. Basic familiarity with discrete structures such as undirected and directed graphs, bipartite graphs, hypergraphs will be assumed. For most of the talk, no group theory beyond the concept of the symmetric group will be required.
University of Chicago
Combinatorics and Theoretical Computer Science seminar
Date: Tuesday, November 24, 2015
Time: 3:00pm
Place: Ryerson 251
Speaker: Lszl Babai (University of Chicago)
Title: Graph Isomorphism in Quasipolynomial Time II: The Design Lemma
Original subtitle: "The `Split-or-Johnson routine'"
Abstract (updated after the talk to reflect actual content and the decision to add a third part to the series):
In this second talk of the series we present the proof of the "Design Lemma," a canonical partitioning algorithm required for the master algorithm. The input to the algorithm is a k-ary relational structure with non-negligible symmetry defect; the output is either a good canonical partition or a large, canonically embedded uniprimitive coherent configuration. The the key tools are the classical and the k-dimensional Weisfeier-Leman refinement process.
This talk together with the third part of this series (Dec 1) forms a stand-alone module and can be understood without knowledge of the master algorithm outlined in the first talk. Basic familiarity with discrete structures such as undirected and directed graphs, bipartite graphs, hypergraphs will be assumed. No group theory beyond the concept of the symmetric group is required.
The University of Chicago
Group Theory seminar
Date: Thursday, November 12, 2015
Time: 4:30 pm
Place: Ryerson 251
Speaker: Lszl Babai (University of Chicago)
Title:
A little group theory goes a long way: the group theory behind recent progress on the Graph Isomorphism problem
Abstract:
The Graph Isomorphism (GI) problem asks, given two graphs with n vertices, decide whether or not they are isomorphic. This is a classical algorithmic problem that has received considerable attention in the theory of computing because of its unsettled complexity status within the P/NP theory.
The asymptotic theory of finite permutation groups plays a central role in the study of this algorithmic problem, thanks especially to Luks's seminal 1981 paper. In 1983, Luks proved that the GI problem can be solved in exp(nlogn−−−−−√) steps. This remained the state of the art for over three decades.
The speaker's recent result brings this upper bound down to quasipolynomial, i.e., exp((logn)c). In the talk I will outline some elementary (modulo Schreier's hypothesis) group theoretic results that are at the heart of this development, and try to give some indication of their relevance to the algorithmic problem.
The University of Chicago
Combinatorics and Theoretical Computer Science seminar
Date: Tuesday, November 10, 2015
Time: 3:00pm
Place: Kent 120
Speaker: Lszl Babai (The University of Chicago)
Title: Graph Isomorphism in Quasipolynomial Time I: The "Local Certificates algorithm"
Abstract:
In a series of two talks we outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial (exp(polylogn)) time.
The best previous bound for GI was exp(nlogn−−−−−√), where n is the number of vertices (Luks, 1983). For SI and CI the best previous bound was similar, exp(n√(logn)c), where n is the size of the permutation domain (the speaker, 1983).
In this first talk we give an overview of the algorithm and present the core group-theoretic divide-and-conquer routine, the "Local Certificates algorithm." Familiarity with undergraduate-level group theory will be assumeda

The Unreasoner
12-22-2015, 12:52 PM
So while I think I get the isomorphism algorithm, I haven't been able to verify its speed. And I'm not sure I'd be able to answer any of your questions on it (yet). He keeps bringing it back to group theory, but I think doing it with sets of functions and sets of matrices might be more intuitive (and closer to what we've been doing.

Meanwhile, something fun for the holidays.
The Kakeya Needle problem (because they look like pine needles obviously, and because of the difficulty in turning a cut Christmas tree in a dense forest):
http://m.youtube.com/watch?v=j-dce6QmVAQ

The Unreasoner
12-31-2015, 03:55 AM
So is anyone reading this thread? I'm not being needy, but if I'm just pissing people off by regularly bumping it, I'll stop. Or someone else can take over with their own areas of expertise.

Or does anyone have any questions? Without trying to be arrogant, I really am a reasonably talented and competent mathematician, and (imo) a passable teacher. I'm happy to answer questions.

Or maybe move on to another topic? To quickly wrap up Boolean stuff: the true number of unique formulas is substantially less than 70 million, because that figure contains things like (a OR b) AND (a OR NOT b) AND a. Circuits are another way of considering SAT, either real physical circuits or mathematical abstractions. It's a common way to measure a function's complexity. Either the total number of circuits needed is counted (sometimes you even restrict everything to two input NAND gates (a v b), from which you can make AND, OR, NOT, XOR, IFF...) or you look at the depth in series circuits (levels of nesting, indicating the time complexity) and width in parallel circuits (space complexity). CNF for instance is massively parallel. So is DNF, for that matter. Some people working in optical/photonic computing believe it may be possible to use these basic facts to solve NP complete problems in linear time (but exponential space). If anyone is a fan of redstone in minecraft (or likes to build simple chips to run DIY projects), studying Circuit SAT is a profitable activity.

The current state of the proof of P vs NP is essentially:

If they are equal, the field is mostly open, except SAT cannot be solved in linear time. Some problems (like the Traveling Salesman) have powerful heuristics, while others (like Clique) cannot have powerful heuristics, or even mediocre ones.

Proving that they are not equal, while it is generally assumed to be true, seems to be far off. We now know that any such proof requires mathematics not yet conceived (iow, we know no tools currently available are up to the task). The last attempt to be given a serious chance was based on circuit complexity. Specifically, someone showed that any algorithm for the Clique problem cannot have a small circuit if it only uses AND and OR gates. This got a lot of traction, and people assumed (or maybe 'hoped' is more accurate) that it was only a matter of time before he extended it to NOT gates as well (because, unlike the NAND gate, AND and OR by themselves are not functionally complete: there are functions you cannot construct with just the two). This would have (more or less) sealed the deal.


So, what now? Another specific problem (Traveling Salesman, Clique)? Another topic altogether? I couldn't cover any topic in mathematics, but I think you (and I) would be surprised to see how many I actually can.

Here's a few that I'd be happy to go into, are example heavy, and be able to answer (almost) any questions you might have:

The Four Color Theorem (with basic topology and graph theory)
The Goldbach Conjecture/Riemann Hypothesis (to teach number theory)
Various topics in statistics/probability/combinatorics (illustrated with gambling games and tge bond markets and stock option pricing)
Classical cryptography (with Kryptos as the example)
Modern cryptography (with Bitcoin and some of the Snowden revelations (Dual EC) for the examples)
Game theory (with the 2012 GOP primary as the example)
Lattices and Fourier analysis (not really related to each other, but both related to the example that is Terezian analysis)
Algorithms and heuristics (we'll use some finite automata as examples)

There are probably more I could pit together a good syllabus for on short notice, so feel free to ask.

Or one of you take over the thread. That was the original plan. I like to learn too. Or maybe a joint effort course?

Frenzy
12-31-2015, 10:44 AM
i'm reading this, but it's all going over my head. i haven't taken a pure math class since high school Calculus in the early 90s, and the closest i come to pure math these days is helping my son with his Geometry homework.

The Unreasoner
12-31-2015, 11:15 AM
If you have any questions, feel free to ask. I also take requests, and could probably find specific examples (charts, youtube videos, articles) to clarify things left unclear. I probably could have picked a better topic to start with, but this is close to what I do for a living anyway, and I've been enjoying myself. Part of me always wanted tobe a math professor. But I realized I might be the only one having fun, and thought I'd test the water.

That being said, the original plan was to have several posters cover topics of their choice. And I think I closed it off nicely this first round, so I think I'll wait a few days, answer any final questions, and then let someone else have the floor (if they want it). If they don't, but still want the thread updated, I'll cover the Four Color theorem next, barring a request for something else. Much less jargon or technical complexity, far more intuitive. It may not even seem recognizable as mathematics.

The Unreasoner
01-07-2016, 03:46 PM
So it looks like EM drives aren't a real thing, despite what recent articles led me to believe. Apparently the measured thrust is within the margin of measurement errors.

That being said, unless some has questions about complexity theory or Boolean algebra, or wants to take over the thread with their own area of expertise, I will start the next topic tomorrow (Four color, unless someone wants to request something else).

GonzoTheGreat
01-08-2016, 03:50 AM
So it looks like EM drives aren't a real thing, despite what recent articles led me to believe. Apparently the measured thrust is within the margin of measurement errors.
Well, duh!
From what I've read of it*, their propulsion was to be generated by assuming that Newton's "action is minus reaction" didn't apply if you simply left it out of your calculations. I'm not particularly surprised that this works better on paper than in reality.

* Note: I base this assessment on a description and the schematics of the EM drive that I've seen on the Net. If that description was incomplete, then it may be that there is another problem with the concept, rather than the one that was apparent to me from the sales presentation.

The Unreasoner
01-08-2016, 10:53 AM
I'm not a physicist. And the first I heard about this thing was that it got positive test results from NASA. I vaguely thought it might work like those tinfoil glider things.

I didn't know until I looked into it that it's almost certainly a hoax. Why NASA even bothered to test it, and why several normally reliable news sources failed to convey the information that this thing is about as credible as that cold fusion thing by that Italian guy, I do not know.

GonzoTheGreat
01-08-2016, 12:26 PM
Correction to what I wrote in my previous post: I think now that I saw the description of the EM drive in a New Scientist. Which is more trustworthy than a random web page, but not on a par with a peer reviewed article.

The Unreasoner
01-12-2016, 03:49 PM
The Four Color Theorem was proposed as conjecture by a math student (I forget his name) around 100 years ago. The student noticed that any map he had to color never needed more than four colors to ensure that each region was colored differently than all regions it shared a border with. He brought this to his instructor, who was intrigued, but neither of them could prove it. It was one of the most falsely proved theories for quite some time (both for and against).

The actual proof is far too complicated to go into here (at least in its current form), mainly because it was one of the first proofs to be largely aided by a computer. Mathematicians broke down the infinite set of possible maps into thousands of 'families', then had a computer check each one. The proof is valid because the reasoning was sound, and the algorithm was correct (we won't go into metaproofs).

The theorem has almost no practical use. While it is true that any planar region broken up into contiguous pieces (like a puzzle) can be colored with four colors, it is possible that those valid colorings can be slightly hard to find. Also, real world maps have three issues (or rather, potential issues) that may render the theorem inapplicable. But first, some examples:

Four coloring of the continental US:http://web.stonehill.edu/compsci/lc/four-color/usa.gif

A false counterexample:
http://tdboui.com/blog/wp-content/uploads/2012/06/morons-on-math.jpg

Another false counterexample, and the corrected version:
https://upload.wikimedia.org/wikipedia/commons/thumb/a/a6/4CT_Non-Counterexample_1.svg/2000px-4CT_Non-Counterexample_1.svg.png

http://upload.wikimedia.org/wikipedia/commons/7/7a/4CT_Non-Counterexample_2.svg

The Unreasoner
01-12-2016, 04:27 PM
Sorry. Didn't realize that one was so damn big. And I screwed up the spacing on the US one, but for some reason the edit button is missing, so we'll all have to deal.


Anyway, in order to understand the topics at hand, two ideas worth keeping in mind:

What matters is shared borders, not common corners. Also, the actual shape of the map is mostly irrelevant. The only relevant fact is shared borders. This means we can smoothly deform (or really, continuously deform, the derivative need not be continuous. If two figures, surfaces, or n-dimensional shapes can be described by a continuous function, and the difference between the functions is continuous, they are topologically more or less the same. Homotopic is the technical word. This has to do with the Poincare Conjecture as well, proved by Perelman. It says any finite n-dimensional shape wothout holes is homotopic to an n-dimensional sphere). So consider this:

https://www.mathsisfun.com/activity/images/coloring-9.gif

Sometimes it helps to work with more rigorous tools, for that we change the map to a graph (mathematical graph, not the plot/picture of a function):

http://world.mathigon.org/resources/Graph_Theory/fourcolour.png

Those who were around for part one may think that this is familiar. Specifically, deciding whether or not a particular graph is colorable in three colors is NP complete. One important point is that the graphs for 3-colorability need not be planar (so lines/edges can intersect) while for the four-color theorem, they must be. This can be seen intuitively if you try to draw a map corresponding to a graph with such an intersection: at that point, you would need to have two countries in the same place. Consider the Four Corners in the US: if Colorado and Arizona shared a small border at the point of intersection, Utah and New Mexico could not.

Graphs are useful in understanding the deformations, however, because you can feel free to move everything around as you wish, so long as you do not cross any lines.

The other point is that any region must be considered as an independent node. This means one region cannot be broken up into multiple parts and keep the same color (or at least this cannot be guaranteed. In general, the maximum number of colors needed is four plus the number of regions with distinct parts, though in practice you rarely need so many).

So the three possible issues with four-coloring maps in practice are:

Disjointed regions, like the US with Alaska, or Michigan's separated piece.

Bodies of water, which tend to require the same color. It can be seen, however, that this requirement is exactly the same as the previous one: the bodies of water can be treated as disjointed regions of a single entity.

Two examples:
http://world.mathigon.org/resources/Graph_Theory/colouring.png
As you can see, Michigan is colored differently here (though there is a valid way to color the US with four colors that does not have this problem, see above).

And here, there appear to be quite a few countries underwater:
https://upload.wikimedia.org/wikipedia/commons/5/5d/Five_colors_world_map_%28Malawi_and_African_Great_ Lakes_problem%29.svg

The third issue is the fact that real maps may not be manifolds (projections) of a flat surface.

Now a question: is a map on a globe always four-colorable (ignoring the disjointed region issue)?

Also, a somewhat tricky example you can try yourselves:
http://www.vb-helper.com/FourColorMap1.gif
One Answer (http://www.alternatievewiskunde.nl/fcp/FourColorMap1.jpg)

The Unreasoner
01-12-2016, 04:36 PM
It looks like that world map has a few issues (Japan, for instance), but it gets the point across.

In any case, for the sphere question, the answer is yes. This can be seen if you imagine the Earth stretched and skewed and molded in such a way that a single country (probably easiest to visualize with Antarctica, but possible for even Vatican City) takes up an entire hemisphere, than flatten it into a disc. You will have two maps: one of just Antarctica (or whatever), and another with everything else surrounded by a border of the one country. These maps are both flat, and deforming the globe (or, by the Poincare conjecture, any finite 3d shape without any holes in it) was continuous (so it didn't add or remove any borders).

Now what about maps on a donut?

Also: would anyone like me to walk them through the invalid proofs? Even if invalid, they can help us gain insight into the problem, especially if we look at why. They are also very intuitive.

The Unreasoner
01-12-2016, 05:57 PM
I think I'll give a rough sketch of the proofs anyway.

One that was reasonably well-regarded considered the colorability of a map with only triangular regions. Any polygon can be broken up into triangles, and any region on the map can be continuously deformed into some kind of polygon (not necessarily regular). This can be done in such a way that each triangle's edge is only shared by one other triangle. Obviously, such a map could be four-colored. The (flawed) proof claimed that the triangular map was equally colorable as the arbitrary map it was derived from. While this is technically true, it isn't actually a case of implication (or at least whoever it was couldn't show it was actually an implication). Both statements are true, but the (at least known) direction of the implication went the opposite way.

The other proof is a bit stronger (and I actually personally worked on a version of it, and independently came up with a very strong version that's inductive) but I'll need to draw some diagrams for it, so stay tuned.

Also, any questions? Comments? Some feedback would be appreciated. (Constructive) Criticisms on style are particularly helpful.

The Unreasoner
01-12-2016, 08:25 PM
So for the other proof, consider this diagram:

http://theoryland.com/vbulletin/picture.php?albumid=7&pictureid=133
In a sense, adjacency is transitive. The entire pseudoproof is way more complicated than I remember, and relies on algorithms and finite groups and modularity (I made the thing to demonstrate an algorithm), but here's a rough description (again, not a real proof, not valid, but it gets the idea across, more or less):

Any region or node that is forced to become a fifth color necessarily touches four regions that are forced to be different colors. Since any forcing is always relative, there will always be an affine mapping (possibly more than one) from one coloring on one 'sub map' to another, after adding some adjacency from one to the other. But without that adjacency, any permutation of the color set can be applied to both, simultaneously. And the amount of adjacency needed between two sub-maps is at minimum three shared borders (or edges). Now the 'unproven' part:

Since adjacency is in some way transitive, and since a unique affine transformation is only obtained when there is a sufficient number of shared borders, you can treat any sub-map as a single region. Therefore, the simplest case for a (necessarily) five-colored map is demonstrated above, if one exists. Specifically, it would need to have a region (or node) at one of the pink diamonds, and it must share a border with (at least) four other regions/nodes. That means lines drawn from one to four circles, with no intersections. But, every diamond can only reach three. Therefore, the four-color theorem is true.

Again, the proof is an invalid one. I modified an old one, (and made it substantially stronger) to show some people the potential strength of metaproofs. Basically I showed that if you had an algorithm that colors as the map is converted to a graph, step by step, there would only ever be three regions on the outermost border of the map (if you treat regions of the same color as a single region). The main problem with my version of the proof is that it required an abstract version of the map where two regions could exist in the same space, and I never bothered to show (nor did I really see how to show) that this didn't fundamentally change the problem.

GonzoTheGreat
01-13-2016, 03:34 AM
What matters is shared borders, not common corners. Also, the actual shape of the map is mostly irrelevant. The only relevant fact is shared borders. This means we can smoothly deform (or really, continuously deform, the derivative need not be continuous.

https://www.mathsisfun.com/activity/images/coloring-9.gif
Note: some changes in weather patterns may result if you do this in reality. Still, it would be fascinating to hear the politicians try to come to grips with it, if they one day wake up to such a new situation.

The Unreasoner
01-13-2016, 11:01 PM
First off, I'm not a programmer. I can write a bit in C and Fortran (and java, but I don't think that will work here), but for the most part, when I need some specialized process done (iow, that can't be done by excell (side note, you can build a SAT circuit in excell. Or even something more conplicated using operators other than and/or/not. It's actually kind of fun, very visual) or the modelling software I work with), I just map it out and someone else builds the tool.

But I'm on my own here. I need to build some kind of tool to process a certain type of large file (like maybe around 1 gigabyte). The specific operations it would need to do I can code. But do any of you know how to bundle it together? Excell can't handle the data. The modelling software can, but it's slow and inefficient. Is there a way to build a simple program (with some kind of command line interface) that processes a few million entries then pauses, displays stats, and resumes after getting revised intructions? How would the data be stored? I was thinking a basic text file with each entry in a specific line, that was treated like a tape in a Turing macine might work, only keeping what it needs atm in memory. But is that the best way, in terms of efficiency? I have 8 gigs of RAM available atm, does this mean I should/can store the entire file in memory? While I can translate algorithms to code, I honestly have no idea how to turn a handful of algorithms or routines into a cohesive program. Certainly not efficiently. Can I overclock my cpu within the program? Will overclocking normally let those extra cycles be used by a program I made without programming in the possibility?

jarno87
01-14-2016, 02:28 AM
I do quite some programming, mostly scientific programs at work. And usually they involve a lot of data, easily several to tens of GB. So some tips.

First off, I'm not a programmer. I can write a bit in C and Fortran (and java, but I don't think that will work here), but for the most part, when I need some specialized process done (iow, that can't be done by excell (side note, you can build a SAT circuit in excell. Or even something more conplicated using operators other than and/or/not. It's actually kind of fun, very visual) or the modelling software I work with), I just map it out and someone else builds the tool.

But I'm on my own here. I need to build some kind of tool to process a certain type of large file (like maybe around 1 gigabyte). The specific operations it would need to do I can code. But do any of you know how to bundle it together? Excell can't handle the data. The modelling software can, but it's slow and inefficient. Is there a way to build a simple program (with some kind of command line interface) that processes a few million entries then pauses, displays stats, and resumes after getting revised intructions?

Most of the tools we write at my work are command line programs, as they are the easiest. One of the arguments would be the filename of the file containing all your data. My usual approach would be to break things down in three parts:
- First read in/preprocess your data, and store it in memory if it fits, just in a large array (in C/C++, use fopen, fread,fclose and new[] for creating the array)
- 2nd step do your calculation
- Print your statistics to the standard output using printf(). Or write them to some text file.
If the processing is such that you would only need to read each part of your data once, you can integrate the firs and second step, and process the data in small blocks, just keeping aggregated results.

I wouldn't recommend programming pausing and allowing renewed instructions. This probably requires parsing command by hand and that is a big hastle. Just exit after showing results. If needed the user can just rerun the program/command with adjusted parameters


How would the data be stored? I was thinking a basic text file with each entry in a specific line, that was treated like a tape in a Turing macine might work, only keeping what it needs atm in memory. But is that the best way, in terms of efficiency?
Text representations of data take usually more space than the raw once. A normal integer is 32 bits, i.e. 4 bytes but written out might take many characters. Furthermore, this requires converting between numbers and strings and v.v. all the time which is very inefficient. If needed I would recommend storing information in some binary format. (Using fwrite/fread)



I have 8 gigs of RAM available atm, does this mean I should/can store the entire file in memory?
Preferably yes, make sure to compile your program for 64 bits. On linux that would be the default, on windows check your compiler settings. Nowadays it is very easy to use large arrays, if your computer has sufficient RAM. Makes the programming much easier. I have processes using 2 to 10 GB all the time, with exceptions going as high as 100GB on a 128 GB RAM machine.


While I can translate algorithms to code, I honestly have no idea how to turn a handful of algorithms or routines into a cohesive program. Certainly not efficiently. Can I overclock my cpu within the program? Will overclocking normally let those extra cycles be used by a program I made without programming in the possibility?
Overclocking is not something you do in a program. Usually this is done in the BIOS/UEFI settings. It then starts your computer with the processor always a certain % faster. So yes any program would use the extra cycles, they don't have to/ cannot be aware of this. A normal user program is not able to overclock your processor. However, overclocking comes with risks to your processor and system stability. If you don't know what you are doing ,stay away from it. In most cases it would not give you more than 10 to say 30 % extra anyway, so just let it run a bit longer.


Hope this helps.

GonzoTheGreat
01-14-2016, 03:30 AM
Most of the tools we write at my work are command line programs, as they are the easiest. One of the arguments would be the filename of the file containing all your data. My usual approach would be to break things down in three parts:
- First read in/preprocess your data, and store it in memory if it fits, just in a large array (in C/C++, use fopen, fread,fclose and new[] for creating the array)
- 2nd step do your calculation
- Print your statistics to the standard output using printf(). Or write them to some text file.
If the processing is such that you would only need to read each part of your data once, you can integrate the firs and second step, and process the data in small blocks, just keeping aggregated results.
I could be wrong, but I have the impression that it isn't really known in advance what precise settings would be needed, but that this should become clearer when the program runs with somewhat flawed settings. So then restarting with an updated settings file would make sense.

In such a case, it may be more efficient to store the actual data (not the settings) in some "raw" format, basically as a memory dump.
If true, then you should first work out how you want to store your bulk data in your program, then write a program to read it in from whatever format it is now (probably a text file of some kind) into an array of the type you would you in your actual program, and dump this into a file. That would hopefully be smaller than a full text file, since text isn't really an efficient storage format (though it is a very versatile one). However, this depends on what kind of data you're dealing with. If it is lots of numbers, then this procedure would be useful. If it is a large bulk of Swahili text, then keeping it as plain text would probably be best.

Next, you would almost certainly want to have at least two separate files: one with the data, and one with the settings that you can change to do whatever fiddling you can't leave to the program. I think that a third file, with the results, would be advisable as well.

So, you would have a program with (at least) three command line options: the data file, the settings file and the output file.

Depending on the type of task, I would use either C (probably C++ light, for this) or Fortran, with a greater likelihood of me using C++ nowadays. But if what you have to do is mostly lots of calculation, then Fortran might be the best option.

The Unreasoner
01-14-2016, 03:21 PM
Thanks you guys. Working on the preprocessor now. The data is technically a directed graph, where each node has an associated 2d table and string (other than its number/name). Right now it's in a csv text file for the nodes and edges, and another csv for the associated data. And I'll have to find out how that one was written, because most of the tables are 64x64, while the rest are 4x4. The entries are mostly functions and variables, though some variables are integers, and some are strings. And the 4x4 are floating point. Is an array of arrays efficient? Or should I call on several distinct arrays (assuming I go with Gonzo's suggestion on the memory dump, and jarno's on compiling for 64 bits)?

ETA: I repped you both, but am on my phone so I couldn't comment. But thanks for your help.

GonzoTheGreat
01-15-2016, 03:37 AM
I think that an array of arrays would be slightly more efficient, but I doubt the difference would be noticeable unless you paid really close attention. Speed improvements would depend far more on choosing the right overall algorithm, and on figuring out which things can be most efficiently done once instead of a hundred million* times. In general, computers are very good at array manipulation, because it is such a common problem. All processors that I know the machine code of have been optimised for this to a great extend. On the other hand, using a number of arrays would at most add a small bit of overhead, if you set it up correctly. So even if you don't use this optimised approach here, the difference wouldn't be anywhere near as big as the gains you could get from doing it in a way that is easy for you. Unless you really botch your algorithm, in which case you're screwed even with full optimisation anyway.
So this shouldn't be much of a worry. Of course, I would think about it anyway; but I like excessive optimisation.

* Suppose you have to multiply three numbers from different data sets; let's designate those sets A, B and C, with individual numbers from each a, b and c. Then you would have to get the result a*b*c for each combination. Now, if set A has a hundred million members, and sets B and C have four members each, then it would be a lot more efficient to calculate d=b*c outside the inner loop, and multiply that with each individual a only. But how to achieve such improvements I'll leave up to you; I don't know your actual problem after all.

The Unreasoner
01-20-2016, 04:50 PM
So I'm kinda busy right now, but quickly on map coloring:

Coloring a torus requires 7 colors. I'll look for an example. But this can be seen intuitively (if you take FCT as given) by embedding the torus in the plane and forcing one region in the intersection of the boundaries. You can try cyllinders and mobius bands yourselves if you want further practice. There is no 3d analogue with shared faces. You can think about jenga towers and their extensions to see why.

And just so I don't forget, I want to do Terezian analysis next:
https://upload.wikimedia.org/wikipedia/commons/thumb/2/27/Lattice-reduction.svg/450px-Lattice-reduction.svg.png

The Unreasoner
01-22-2016, 09:52 AM
For those that haven't seen Pixels:

9944
Σ f(x)=f(25872248)
x=1

What is f(x)?

GonzoTheGreat
01-23-2016, 03:27 AM
f(x)=2601.794851166532582461786001609

Admittedly, that's a bit trite, but it does work. :p

Nazbaque
01-23-2016, 03:40 AM
f(x)=2601.794851166532582461786001609

Admittedly, that's a bit trite, but it does work. :p

No it doesn't. f(x)=0 would be the trite answer.

The Unreasoner
01-23-2016, 03:40 AM
Lol. I didn't have that one. There are infinite answers though.

It's the question I submitted for the employee screening test.

The most common correct answer is f(x)=0. The one I haven't seen yet is f(x)=xth prime. I'll have to take a look at yours when I'm less tired.

The Unreasoner
01-24-2016, 01:33 PM
f(x)=2601.794851166532582461786001609

Admittedly, that's a bit trite, but it does work. :p
lol. I think you missed the fact that the right side is also within the function. The simplest linear answer (other than f(x)=0) is f(x)=x-(23574292/9943).

ETA:
I love the question because they know it has infinite answers, while some of them are more interesting than others. It almost functions like a personality test. Someone who gives f(x)=0 is a smartass. Someone who uses Gonzo's answer plus the floor function (to make it work. And I have seen this one) seems to be adaptable. Someone who gives the general form of the linear solutions is meticulous. Someone who does the same for the geometric series is a show-off.

Nazbaque
01-24-2016, 02:46 PM
f(x)=sin(x*pi)? Smart ass squared?

The Unreasoner
01-24-2016, 06:25 PM
f(x)=sin(x*pi)? Smart ass squared?
f(x)=(x+1)! mod 2

Smartass factorial.

Nazbaque
01-25-2016, 04:45 AM
f(x)=(x+1)! mod 2

Smartass factorial.

f(x)=cos((x+1)*pi/2)?

The Unreasoner
01-25-2016, 10:31 AM
f(x)=cos((x+1)*pi/2)?

That's pretty good. But you can do better. This repeats every four terms. But 8 is the largest common factor. I'm looking at a model for elliptic curves over finite fields right now to take advantage of the fact that the right side is 1 plus a prime.

GonzoTheGreat
01-25-2016, 11:01 AM
f(x) = tan(x!)

Proving that one wrong wouldn't be a trivial matter, I think. Possible, I suspect, but it would require very high precision calculations.

I admit that in my previous answer, I'd overlooked that the function appeared on both sides.

The Unreasoner
01-25-2016, 11:38 AM
Did you mean to put a pi in there?

And either way: do we just need to prove it wrong, or do we need to actually evaluate either side?

Nazbaque
01-25-2016, 11:48 AM
That's pretty good. But you can do better. This repeats every four terms. But 8 is the largest common factor.

But that would have been showing off. With pi/2 you just get 0+1+0-1... which eventually cancels out unless the number of terms is 4n+2 (4n cancels out by default 4n+1 and 4n+3 cancel out if you start at the right spot). With pi/4 you get those messy ∓1/√2 terms. It's crossing the line to gaudy when a bit more modesty would have had elegance.

Now I'm wondering if you could use f(x)=(1-q)q^(x-1) so that the sum becomes 1-q+q-q^2+q^2....-q^9944 which becomes 1-q^9944 and is in itself relatively neat but then the final equation becomes 1-q^9944=q^25872247-q^25872248 and solving the q in that is something of a pain.

The Unreasoner
01-25-2016, 12:19 PM
But that would have been showing off.
What do you think we're doing here?

Watch:
f(x) = tan(x!)

Proving that one wrong wouldn't be a trivial matter, I think. Possible, I suspect, but it would require very high precision calculations.
(infinity+)
Sigma ((z^25872248)*(e^(1/z))-((z*e^(1/z))*(1-z^9944)/(1-z)))dz
(0)

is not equal to zero.


ETA:
hmm. I forgot about the tan. I'll get back to you.

Nazbaque
01-25-2016, 01:00 PM
What do you think we're doing here?

Showing off, but the goal is not to let others realize it. The goal is to be elegant. If you over do it, you're just gaudy.

The Unreasoner
01-25-2016, 06:44 PM
f(x) = tan(x!)

Proving that one wrong wouldn't be a trivial matter, I think. Possible, I suspect, but it would require very high precision calculations.

Do you know the answer? I can show the infinite series that describes the difference converges to a nonzero value...'probably'. And that took a significant proportion of computer power away from the model builder (turns out after preprocessing and computing common values ahead of time it blew up to 11 gigs).

But doing it by hand requires some identities no one has bothered to work out (and are quite probably analytic).

The Unreasoner
01-25-2016, 07:34 PM
Oh and if anyone is still interested in the Chess CNF, I got it with some circuit script from work:
(AvCv!Ev!G)^(AvDv!Ev!H)^(AvGv!Cv!E)^(AvHv!Dv!E)^(B vCv!Fv!G)^(BvDv!Fv!H)^(BvGv!Cv!F)^(BvHv!Dv!F)^(CvE v!Av!G)^(CvFv!Bv!G)^(DvEv!Av!H)^(DvFv!Bv!H)^(EvGv! Av!C)^(EvHv!Av!D)^(FvGv!Bv!C)^(FvHv!Bv!D)^(AvBvCvD vEvFvGvH)^(AvBvCvEvFvGv!Dv!H)^(AvBvDvEvFvHv!Cv!G)^ (AvBvEvFv!Cv!Dv!Gv!H)^(AvCvDvEvGvHv!Bv!F)^(AvCvEvG v!Bv!Dv!Fv!H)^(AvDvEvHv!Bv!Cv!Fv!G)^(AvEv!Bv!Cv!Dv !Fv!Gv!H)^(BvCvDvFvGvHv!Av!E)^(BvCvFvGv!Av!Dv!Ev!H )^(BvDvFvHv!Av!Cv!Ev!G)^(BvFv!Av!Cv!Dv!Ev!Gv!H)^(C vDvGvHv!Av!Bv!Ev!F)^(CvGv!Av!Bv!Dv!Ev!Fv!H)^(DvHv! Av!Bv!Cv!Ev!Fv!G)^(!Av!Bv!Cv!Dv!Ev!Fv!Gv!H)

ETA:
if any of you have miniSAT (free):
c
c THATFUCKINGCHESSTHING
c
c
c DIMACS
c
c
p cnf 8 32
1 3 -5 -7 0
1 4 -5 -8 0
1 7 -3 -5 0
1 8 -4 -5 0
2 3 -6 -7 0
2 4 -6 -8 0
2 7 -3 -6 0
2 8 -4 -6 0
3 5 -1 -7 0
3 6 -2 -7 0
4 5 -1 -8 0
4 6 -2 -8 0
5 7 -1 -3 0
5 8 -1 -4 0
6 7 -2 -3 0
6 8 -2 -4 0
1 2 3 4 5 6 7 8 0
1 2 3 5 6 7 -4 -8 0
1 2 4 5 6 8 -3 -7 0
1 2 5 6 -3 -4 -7 -8 0
1 3 4 5 7 8 -2 -6 0
1 3 5 7 -2 -4 -6 -8 0
1 4 5 8 -2 -3 -6 -7 0
1 5 -2 -3 -4 -6 -7 -8 0
2 3 4 6 7 8 -1 -5 0
2 3 6 7 -1 -4 -5 -8 0
2 4 6 8 -1 -3 -5 -7 0
2 6 -1 -3 -4 -5 -7 -8 0
3 4 7 8 -1 -2 -5 -6 0
3 7 -1 -2 -4 -5 -6 -8 0
4 8 -1 -2 -3 -5 -6 -7 0
-1 -2 -3 -4 -5 -6 -7 -8 0


ETA2:
Does anyone remember where RJ talked about using Boolean logic to work out the cultures in WoT? Terez's thread (and this one) made me remember it.

GonzoTheGreat
01-26-2016, 02:57 AM
Do you know the answer? I can show the infinite series that describes the difference converges to a nonzero value...'probably'. And that took a significant proportion of computer power away from the model builder (turns out after preprocessing and computing common values ahead of time it blew up to 11 gigs).

But doing it by hand requires some identities no one has bothered to work out (and are quite probably analytic).
I would say that it is almost certainly false. Both sides of the equation are as near to random values as makes no difference, but if you want to actually be certain (rather than guessing, which isn't how mathematics should work) then you have a problem. You would need to calculate extremely big factorials, then figure out precisely how often Pi fits into those results, calculate the resulting tangents and finally start adding (or subtracting) them all. The tangent thing and the additions are trivial (apart from also having an infinite number of decimals involved), but the "modulo Pi" bit is where things get really non-trivial. It is a trick I learned from a book by Richard Feynman, who himself learned it from a fellow who was even cleverer than he was.

The Unreasoner
01-27-2016, 05:11 PM
I would say that it is almost certainly false.
Yeah. On my second pass I thought 'that can't possibly be true'. But as you note, in mathematics, that sentence only works if you mean it literally.

It is a trick I learned from a book by Richard Feynman, who himself learned it from a fellow who was even cleverer than he was.

It looks like some stuff I've seen from von Neumann. Probably the greatest mathematician since Euler, along with Godel.

The Unreasoner
01-27-2016, 08:48 PM
On the model-builder:
I'm using a quad-core processor with two threads per core. But the program never seems to use more than one thread (even when nothing else is running, it just jumps between 12 and 13 percent of processor time). Did I fuck up compiling? Or does each thread need to be called on explicitly?

jarno87
01-28-2016, 01:43 AM
On the model-builder:
I'm using a quad-core processor with two threads per core. But the program never seems to use more than one thread (even when nothing else is running, it just jumps between 12 and 13 percent of processor time). Did I fuck up compiling? Or does each thread need to be called on explicitly?

In general, programs don't use more than 1 core automatically. It has to be programmed in specifically. One of the reasons is that the code must be Thread-safe (google it), and so satisfy some requirements (to avoid race-conditions, for one). There exists frameworks to help you do this for big computations, like MPI, but they have their own requirements.

So the short answer: yes you have to create each thread explicitly. Depending on the program this doesn't have to be a lot of work. I have made an existing program multi-threaded in an hour, once. However, it was quite suitable and well written when I started.

The Unreasoner
01-28-2016, 01:37 PM
(google it)
lol.
So the short answer: yes you have to create each thread explicitly. Depending on the program this doesn't have to be a lot of work. I have made an existing program multi-threaded in an hour, once. However, it was quite suitable and well written when I started.
Thanks. When I finished the preprocessing, it was made so that nothing was used twice until the end. So I just split the data into different smaller arrays and ran multiple instances. Still only hovering around 50%, but it's a significant improvement. I'll have to look and see if I can make the last step 'thread safe'.

The Unreasoner
01-28-2016, 01:45 PM
but the "modulo Pi" bit is where things get really non-trivial.
I meant to say this earlier:
Computationally difficult, but not the hardest mathematically. The factorial is a pain, but you can work with it. And over any finite set, you can create a lattice basis that includes both integer multiples of Pi and the multiples of the integers. When I was working on it the hardest part seemed to be getting the product of the sin values. And then you have to hope the function never zeros out over the positive real numbers, because then you need to take a cosine integral (which, as we've stated, is NP-Complete).

The Unreasoner
01-28-2016, 02:43 PM
ETA2:
Does anyone remember where RJ talked about using Boolean logic to work out the cultures in WoT? Terez's thread (and this one) made me remember it.
Took awhile to find, but here:
Therese Littleton

Are there particular historical eras that influence your stories?

Robert Jordan

Well, to give you an example of the way these things work... the Aiel. They have some bits of Japanese in them. Also some bits of the Zulu, the Berbers, the Bedouin, the Northern Cheyenne, the Apache, and some things that I added in myself. They are in no way a copy of any of these cultures, because what I do is say, "If A is true, what else has to be true about this culture? If B is true, what else has to be true?" And so forth.
In this way I begin to construct a logic tree, and I begin to get out of this first set of maybe 10, maybe 30 things that I want to be true about this culture. I begin to get around an image of this culture, out of just this set of things, because these other things have to be true. Then you reach the interesting part, because this thing right here has to be true, because of these things up here. But, this thing right here has to be false, because of those things up there. Now, which way does it go, and why? You've just gotten one of the interesting things about the culture, one of the really interesting little quirks.
To me, that in itself is a fascinating thingthe design of a culture. So that's how the Aiel came about. There are no cultures that are a simple lift of Renaissance Italy or 9th-century Persia or anything else. All of them are constructs.

The Unreasoner
02-02-2016, 01:31 PM
The program is taking a ridiculously long time to run. And apparently web surfing cuts efficiency dramatically. One block completed in 28000 seconds while I was sleeping. Another is running now, and we're up to 123000.

Was the guy Von Neumann?

The Unreasoner
02-14-2016, 01:52 AM
So it takes over an hour to read in the data after every iteration...should I just learn how to program in pauses and prompts? Or would the speedup of not restarting each iteration not be worth it?

GonzoTheGreat
02-14-2016, 03:16 AM
It might be worthwhile to try to figure out why it takes so long to read. Maybe it will help you come up with a more efficient reading mechanism. If you're really lucky, it could even be something that would be useful in some other cases too.

The Unreasoner
02-15-2016, 02:26 PM
The problem may be that it's in a text format (predicting the type and location of the outputs seemed like a pain in the ass). Or that I didn't actually 'compile' anything in the end, I decided instead to use some tool a friend had that let me use either Fortran or Maple's language (which I am most comfortable with). I'll run it by some people who have some specific knowledge of the problem I'm working on. Though he hates being bothered, so it would be nice to have something to show him.

Anyway, on Terezian analysis:

So apparently my lattice idea is, and I quote, 'fucking stupid', mostly for reasons I was aware of. The person I ran it by said while it might be the way to go in theory (though we had a debate on the efficiency of regression techniques I would rely on to sort elements into spines), in practice it is too slow. He did like my original idea (encoding music into an image, then using various techniques for finding edges, eigenfaces, and stegonographic information to build the metrics and operators), but mostly because it draws on some fields that are well-understood and documented. I'll walk you guys through both if you care, or I can give it another pass first. Also, something crawled across my feeds today that may be worth looking into for guidance:

http://blog.leapmotion.com/wp-content/uploads/2016/02/Lyra.gif

GonzoTheGreat
02-16-2016, 02:25 AM
The problem may be that it's in a text format (predicting the type and location of the outputs seemed like a pain in the ass). Or that I didn't actually 'compile' anything in the end, I decided instead to use some tool a friend had that let me use either Fortran or Maple's language (which I am most comfortable with). I'll run it by some people who have some specific knowledge of the problem I'm working on. Though he hates being bothered, so it would be nice to have something to show him.
I could be wrong, but I don't think the problem is one of interpretation instead of compilation here. Reading in text files is a bit of a pain anyway, so for that the disadvantage of using an interpreter is lower than it would be for the actual computations.
What might be the problem (though I don't know your code, so I'm guessing based on ignorance*) could be the way you add each newly read item to memory. If that involves rearranging the whole rest of what was already read, then you've created an N-squared mess right there. And if it also means making memory assignments, then it would be a very inefficient N-squared mess to boot. If this is the case, then the solution would be: first read, then sort in place.

* Which, of course, is the best kind of guess to make. It gives one oodles of plausible deniability, and if one is right then that's amazing.

The Unreasoner
03-04-2016, 03:45 PM
Okay, I think the problem is the fact that I'm treating some very large lists as sets. A few thousand sets with a few thousand elements in each. So, since I'm using the Maple language for those, I'm guessing that Maple doesn't check for duplicate elements very efficiently.

The Unreasoner
03-04-2016, 03:47 PM
As for this:


http://blog.leapmotion.com/wp-content/uploads/2016/02/Lyra.gif

They don't have anything really novel in terms of audio encoding.

The Unreasoner
03-04-2016, 10:43 PM
When I compile it's too slow, and when I use the interpreter it can't read in efficiently. I can't even begin to describe how pissed I am. I'm ready to fucking crucify someone for this. And if it's me, so be it. As long as someone bleeds.



Anyway, on a lighter note, something I've worked on before is reversible computing as SAT. It's closer to what we've done before in this thread, and pretty interesting in its own right. Unless someone wants to take over, or wants to see the Fourier+lattice techniques for music theory (so we'll ignore computability issues), or wants this thread to die.

Nazbaque
03-04-2016, 10:52 PM
How can you crucify yourself? Suppose you manage to nail down one hand, what will you nail the other hand with? The first hand being full at that point. Of bloody nails that is. Not the kind at the ends of your fingers. Man there are a lot of puns in this line of thought.

GonzoTheGreat
03-05-2016, 03:15 AM
How can you crucify yourself? Suppose you manage to nail down one hand, what will you nail the other hand with? The first hand being full at that point. Of bloody nails that is. Not the kind at the ends of your fingers. Man there are a lot of puns in this line of thought.
Design a Rube Goldberg Contraption to fire off the right number of nail guns at the same time, then stand in front of it and start the thing. If necessary, rebuild it so that you can actually reach the starting mechanism from where you're standing waiting to be crucified.
No problem, apart perhaps from some engineering stuff which a proper scientist dismisses as "trivial".

The Unreasoner
03-16-2016, 10:14 PM
As Gonzo notes, designing a crucifixion machine is basically just an engineering problem, and well within the scope of this thread. Though my Catholic background compels me to note that the nails don't actually go through the hand (you can ripthe hand away). They gobetween the major bones in the forearm.

Why can interpreters run in multiple threads without special coding?

Also, I might get to reversible SAT later, but anyone's interested in Terezian analysis...
Geometry of Music
Sunday, February 14, 2016: 10:00 AM-11:30 AM
Marshall Ballroom West (Marriott Wardman Park)
Dmitri Tymoczko, Princeton University, Princeton, NJ
In my talk I am going to build on my earlier work into the non-Euclidean geometry of Western harmony (work which led to two papers published in Science, the book "A Geometry of Music," published by Oxford University Press, and an interactive sculpture in the National Museum of Mathematics in Manhattan). I will show how the mathematical notion of a "vector" corresponds to what musicians refer to as a "voice leading." Once we understand this correspondence, we can use mathematical and computational tools to study the vectors found in musical structure -- leading to new insights about musical style and also particular pieces. I will show how these vectors are crucial to understanding the geometrical structure of musical harmonies, and how that geometrical structure in turn helps us expand our conception of a musical vector. And we will develop new insights into the Renaissance composer Luca Marenzio's musical representations of the afterlife.

This happened. Apparently he was light on details, but perhaps worth looking into if I can find any specifics on his work. Or I could just ask him...

Anyway: one of the above, or another pass at Kryptos?

Nazbaque
03-16-2016, 10:39 PM
As Gonzo notes, designing a crucifixion machine is basically just an engineering problem, and well within the scope of this thread. Though my Catholic background compels me to note that the nails don't actually go through the hand (you can ripthe hand away). They gobetween the major bones in the forearm.

I actually am aware of this, but treating these practicalities as obvious would have implied the trial and error kind of experience which led Romans to those practical methods, so I went with the established myth. This was merely to prevent people from seeing me as some sort of nutjob and had nothing to do with my desire to follow the pun chain.

The Unreasoner
03-18-2016, 05:04 PM
Okay, a quick rundown on some mathematics of nonstandard computing. True quantum computers (iow, based on entanglement, not the Canadian adiabatic bullshit) rely on quantum bits that each take the form of a probability distribution. You can set each one independently, and when entangled they are understood by the model of a 2^n dimensional circle. From here you perform a number of flips and rotations to the system until it encodes the problem under consideration. At this point, you perform a quantum operation (like the quantum fourier transformation) that collapses the state. A quantum computer is 'complete' if it has a functionally complete set of logical operators and at least one quantum operator. It's important to note that results are only probabalistic, the qubits are not entirely independent, the functional operators need to be reversible, and the quantum operator is irreversible (you can't uncollapse a state).

There are other nonstandard computing models, like the analog computer the Dutch use to manage their unique water issues. I believe it uses voltage and current to directly model the water. Other models use photonic processes, pneumatic processes, mechanical processes (some of these are really cool. I met a local artist who builds some amazing clockwork computers for collectors), or even purely hypothetical ones.

And the model I am currently trying to design is another. As we've seen, any operation computable by a Turing machine can be reduced to a circuit of AND/OR/NOT gates. But we can intuitively see that more information per 'unit' (bit, qubit, obit) means greater efficiency. As it happens, my model uses sets of elements in a finite field instead of bits. But, with just a little tweaking, we can see that we stil have gates that function like AND, OR, and NOT; and De Morgan's laws still apply. In addition, you can develop special operators that act directly on the elements of the sets themselves (for instance, if the finite field was integers modulo 7, you could have an affine transformation operator). So: AND becomes the intersection of the sets, OR becomes the union, and NOT becomes the complement (sticking with integers modulo 7, the complement of {0,1,2,3} would be {4,5,6}). The empty/null set is analogous to FALSE, and the full set corresponds to TRUE. Partial sets are used to rigorously manipulate discrete probability distributions of nondetermistic variables.

I have to say, I am really fucking proud of the work I've done in the field, and my model will work with certain hardware better than anything else currently out there. Unfortunately the guy in charge of the project just wants to throw computing power at a primitive genetic algorithm to build the model. He has no understanding of what it will look like, what the extra operators can be, and how they behave. So like I said before, I'm on my own.

The Unreasoner
03-27-2016, 09:45 PM
Okay, I was bored and already testing some things in Maple when I decided to take another look at the problem I got hung up on last time. Turns out I just misinterpreted a line (and I confused the technique with another I'm more familiar with. Though the authors could have been a bit clearer in their notation). Turns out s is just twice the target minus the summation of the multiset. And since lambda is just there to ensure what we might call 'technical compliance', we'll ignore it, and just look at the straight residue (as opposed to the quadratic diophantine version). But, to show the relationship:

Quadratic Diophantine:

A*x^2+B*y=C with A, B, C, x, and y all in N (natural numbers).

Since you can assume A, B, and C are all relatively prime (no common factors. And you can assume it because the Euclidean algorithm makes it easy to find gcd(gcd(A,B),C), and you can then just factor it out), you can rewrite it as:

A*x^2=C-B*y

A*x^2 = C mod B

x^2 = C*A^(-1) mod B

Since C*A^(-1) mod B is easily worked out, you can show that if the square of a natural number x is congruent to some number Q modulo N (where Q=C*A^(-1), and N=B), then there exists a solution to the subset-sum problem used to generate Q and N, provided x is less than some positive number t (also generated from the subset-sum problem. It's essentially a holdout of the restriction of the domain on the Quadratic Diophantine prolem).

You find Q using the Chinese Remainder Theorem on the following congruences:

Q=t^2 mod P

and

Q=s^2 mod 2^(m+1)

while N is equal to P*2^(m+1)


P is the product of a set of distinct prime numbers (other than 2) equal in size to the multiset raised to the power m (the number of bits n the summation of all the elements in the multiset), while s is the summation of a set of values obtained with the Chinese Remainder Theorem on the following congruences:

value[i]=multiset[i] mod 2^m

and

value[i]=0 mod P*primeset[i]^(-m)

You must also ensure that the values are not congruent to zero modulo the corresponding prime.


Now, this problem is NP-Complete, which means that it is a deciscion problem. Finding a suitable x only means that a solution to the subset-sum problem exists. To deconstruct the x value into the members of the subsets, you need to test each member (appropriately tweaking the values) and see if the congruence still holds (but these are much easier to do than finding the initial satisfiable x). That being said, here are the Q, N, and t values for the tattoo problem, along with a satisfying x:

Q=
13336001699742420686934233547272257409195346594156 82724534116136000988597221417465786711259086166981 18171681770816177404214012655963100828749652830208 54284290255887671935141179833791741577165394255213 75283889443416823485393064744585773608773611552790 75397713471851802327593114552596382780605290453652 07339740598748555180385668281023749958339598750179 20885085371761835725344335119084050637212831886860 15401275935321702864399786025

N=
17637633085770622730167837158713586993955291176605 22975805775356565230649360756421710721188160488822 39650926420928748408886434689636325996966686327607 33996956386638348176583805095951413458974055718811 51510682141417609797054161585105219795825853625704 22912499358432081648005992562325172825869068050796 05252968582528272876272691000467076037340989243503 05805319436099832720320261381112451194704105295364 60897537747220000000000000000

t=
14617619954027659287490340612037252463102826513514 76973197696361287780797932664617294740806305686793 85859046671490428808078940755393128988066259149277 37188540029303521452816955002512704789065694036647 13578929639092785029041463685283867334672994721157 83464940159141940503120547586825551777893350315713 84559579256550517603272266403906272756186227781821 64874364346618291695662594231636567551201082790345 54834031231243103645

x=
14617619633525147492129890288700729114868914534751 46277820262346268891743548951014757483385733388587 36365592106335149370810012590102613115015950247250 45588814771855724069959090134347241495837143808517 32054100734545378712219504178935025638417080045028 60889944097138095731539434077244907991703641901644 39733968042396973272497368511048003935827847781320 03469245351589859856719536806406258223874158777088 79853608867961853645


As you can see, even a relatively small problem blows up pretty quickly under repeated reductions.

The Unreasoner
03-28-2016, 12:21 AM
Just for fun, I took a factoring problem as 3 SAT and converted to a Quadratic Residue problem. The number being factored was 6. And look at what I got: 51997253222067379089319540632601559669005042061175 56637289779477435766558348655888120797686376205713 66817852368272041101568515731129459426988680734924 97121123141893672238060887148367921867243470949721 63079195543006011995195942318767451628999722625526 87071685899663428729235205797440768502726473537355 54157638572402310610922543578821807037948401319654 24273783987609525212172854590568202235016380500900 42407964475693355830792419784983592726945270918830 46770756831347192641393664992273321695322733653800 03361167250057574362677508458793019349885303902967 87626528110029131351614600873167912415715149704702 43233437945756842088798003526542646604937257199352 10160049895759890263228607678442225684149482171696 10051048785356980445389901308640159184497630976102 88996010089824079698876214018392650897852234340233 34300955347230657552579292067550390047470887926085 02526366632624033848409555466442603478616726682030 14053722734026306902094104970363760272775110200373 11849782384032944339284846395486410498419090648028 33881533304855686685307809488808927769396228229195 53235033118102247438146849539314772135017055407785 78206387382731276237647539797627942075567378923332 04992471884470732735089484712495313883635424538003 01966523463740104394477564020953790336579957665395 88657254664943914910129366025586001717400425304085 07856217734002436762355936824509443645999112110102 14037942743618506434185787437735043384233822710353 84334936861382942238034695460630193055822868366830 27629401550412605642534807856676367418011018289341 31217918493840474211990621332141467654871399007546 95663668381985876701916386505480438785605410495930 86580782147354481745785233916987938863322422319915 89666666492456743607703253513608238168647116858964 60107306963118407273139670134578632282611769526223 97409831999688284057026248035184181632063802304484 15186127893134727458996161415676313692089013489501 63354646709731320143477067263468330837624231132571 76652087547315628754561647708727287733255138223211 46680223945098166123701546587951204627263282838345 73228471494261794980860279697507002404385651821797 50320886988417375782305930739383957532438770380320 20899347970336207447018032154165048151787882319623 63148554840763070019736423926562196968561869913940 23950183074866735384091396718791767666085869070651 82827413621110086175908108957722215034432772943871 41766195889947123912868933546800605413210535677810 58840918934902194735733145149386232994198408687885 85972563037277331823296720903645043015951511801926 14960819219414570782039191350486544513463989268995 93954282625999559117372461827743204772577681952174 59269487328339670132510596423087551547900798671173 03759685135878120965760345879360889991443648509512 41754388716889769314539003759861700008923784778377 68032229065752565291165546833801177280988980516876 81537665510497875896617378678092024468742502474062 12091347284439862887355384087419991532891322157548 24731514836334447735696171432392862042432441927673 96530941728036695988338209777507635671080216908034 60325197301969892150066746398036436734829762771053 58096518346690456200624705588182133867485901636173 27057788831013467121083658438464404979024480752113 48097523564340090604288106109376793943927329579689 72230906844270750255607811970658542209323296319471 89352570806528426788645065177138364217931122744710 26862722193778821353053013818893241101851519471330 64605286914056966425955336576918424039649119256769 87125287997789651135268843963336432264343360081342 07517179382381712181558124450123142315759960827934 90611550165653740825423450571697487413865654390348 46863626080316271718283180975184785262722936314441 14154682473132458477780234620914385740150920797907 93271825393665431551298462072012945412179440217555 03890066511061684561520088106540049329386938587970 99594658206149704814808846222954635927268934417401 06853169328155586136823939074566453684114676790920 26678925351247955654744468987985594915843012965303 36359134692890981893961579921974306942364335387530 48391449150260449139203641434568421856680754988687 22719724554466374052152614004174566196063495324098 13956325779726304076928848096628549789615870605314 25498889454449274292380882814639431513079824183711 57914239494279631251612153366095718820071646264139 92228656707315091073282806607363195856328332716417 10892266912845427331297950405270764134327957270026 15098239080701142753090420629748270141656700188232 21480062899467188651286964812085914634069546232363 27377377275075566043488484627795322735416825646799 40588066680255416942367131457765072307287597965469 87970602625039203067291653737575974148361699017058 40291548297651859475197732161604311083948893140538 33019998730818246895465741930774868057927431087565 46471741731656522032528185693634221276859909878666 57639226115217310520426492319123856845938371256388 86996852117915994827083247148176993714452661910416 89763622182971150944489675804321670100286257630020 21573985991238363918184725704810962355640098729688 22718865904544455488508528721160921450070926040472 07168710313358895208458930032808659396327924760199 37784820839377707932131068258231993516046692805537 45011678402978080465041155906108362823702754525288 41548400914405203871519511343530073192320710693574 08179044442791846987912315366347211016762585997494 01782350741159922365178502512066101963856357105117 26691125538432589129437965803943697551638617299609 13100972781879698010248786905715630343971390147919 79296554962738863287387015220045340991698372086465 26143115792991727813620289569374240116763684176599 80339371271480039893451531753450773359830695925019 82212838767961629336952732942024617814501651971646 56010174350277628010181322662335693307329716282477 69898319224208474684739538594212533349518540738011 94030590025592758152596818915877595139619457312713 51583360316848118547265469457454424868840909617735 82520144126445312086848015445042273965075132129669 14484077201393998251803012767409133025923966054598 23662596601956951284414217849476795872133629599954 60603456522893500000535470902460120642262009630554 02537785282731343287813814705090555186822641346662 72291003924187411180381092257148790299169896775100 63989869690423383061685618924793310894112884181181 28486849962672143605736814707997570702634253741292 04392411413461858949794346393279272265989401004652 38345533041593956739885874833144163347875470984327 15803298942818793968100493553153594125936582083664 04790258441908007446677624824075223800886425071908 99912962438514863251296961852923549738885804354343 24908773653054491252757836659451344407904304448837 11950271213334975840887368670035253801889103596126 07133623766973256125255393631766296945901467640948 22722230437693236461857174525887577902046631469297 44110431690762669338628174960612365070603176939436 91405828783803260445577883746438526607644476507275 51059101760816247958298851934187819364165199642483 82654342464004503252216157787219613472727885022213 01414016279304038294005798013814855824850379080313 06670105051443369011301772328137165495639027922088 13482583991746626902877151868590237003378133847923 41359733406569853044429806782501154598740264057666 98157264321284774326750119081366794272237027198638 79120466121471710138034770000109842094187629574912 67225713328123847634657580386626624 50041979159546352688215770757832289186196976401792 93946228094774247437087836074210408163448438000612 71534519197992934755672916166655574896812495088682 17382751049302223884942679207645910264780660024820 75618977530990641618793127009136079396528187035312 19830772445717568845309093861459795400062708072542 94654862938685130640207206468014603255385255570482 01015384154403499718548808055729227656862758952944 84773496231180751830672849994253128541519047428877 08113494109876279963543549925030079427522459254109 44510379646255868447450658470120819085952624457613 82086095219172293288350353365144163784416081527200 91545010392974507656008528544809583705290492040349 61803177590765793681978343849719992694284712290970 96392927100948917264336269839663560962123139468562 01977937726318847458153451120562792694460431875875 58590744926134781839427070657656400436887446558356 05492809619773676045399565973216005101188601767010 57673647079806913211841977791330773226049130693364 67504672775020928051228427210876900244594608429718 14424006050293734404900455679728180289080526239456 98233846580360914701015509619654353341052285113767 78867189215981626271621802691297239732819037656590 07927515495465389097033146864896456209687047112866 15301365318669575349322520628217888725015868959303 72933818137982234062714305680544911888983119367243 98552936913953165983634822728560949404372879803013 44476707819765681600221162200870186402878691194847 82141535344846177692360900780648963490237568431809 52377183828760440651581510895634230492697485893798 89649284595024337817345183808787204511120291301150 63488746321230983996829004111068812261680763855309 21811560167927601216105359997449966339422429356865 00430068135625497734629135342722958831970058128600 44800062283015331345880419617868700439583698388186 93680688402223212107350018851850452670069033587028 87416315927930629930101420757936528731343258740864 62004210466773954241660365774025957674297651077530 71267571882595868162238111188374112174828014359026 98051953910561781628769548265079274588685483279334 24301643774153650224582834895787639274279434589720 50122520448959156461190541661972951921723510063366 85345781284838214913558629507497823211247516464335 99854228317148735529649919532056251999310184682417 43009872337644030939681849647533169510570735546897 42328257696626375716687023267793295542587045017211 88796181341138876508815001705513918280184418068728 66742478151801326601916102641804079260477616755398 30822613581111824096566450843475532349259211085623 78248018759072977315592436075742857916701609303451 31483858290325258065009146251565825021883652043000 91849882696322571636186453100092590561937450917454 28620734981216207760687550348044155100941579714346 32357428368466266288295312649665896070511474578197 27523922650156415028758697054549129446863415994934 27964319132493404743640586718878795935812988372291 96227701727992212726453236477311552729464575429057 25251790636130762292690711605878446759903580402023 29188325731002024102216717493783556453976544023741 21297027124608438444580766182111178376051634535087 35042893299098043600044378608996195029034788387129 48128366331448213113372683194479816061097219141870 40245801492771197168348088076478248555379196586557 89328994427932171028678963510577813312731578919345 52643226691358005773487459827294126378003818503192 30060132608736825136352720650211591285608008903031 09518909407407683567811986193496810236708666904846 15012834351851588071752079828118887871197339242042 86005259712990948509127261437378544439416191096809 70262047704456696434150244199098057239928562580181 41570212094588143670170518517990551301718806792742 84288426555449280553185451135234406061504664978883 11582800640891570467807703252771904757966100668390 76271487116116364961669411994006132282249678793435 16515414686579571110078856103814105972204892985951 56011821621514368015138707658063302493599793507402 88317486721430535304270698192502008507489431459146 87412961700862481839740839013941762362540394604401 44849589282574283783962276612202889481512428549760 28716961214334002455946232255967036935979427868981 32659592042055383107724412632901382331294155215191 62511642217439121049425710746737119628408685153187 55352086881877065750699389923198981469464464688387 71027655710423339847474679641975288514104407794731 15573451801739821213542936548705405970443670882016 93759769224731168749686849889048613513209644300851 96658520874074498013841092496530878187451306310547 45289816753951229750864568712284725528023320520079 50407238565491681516855772855780558399456464404388 00694834845459154010492869947452271602874017751099 57834882917493958215956147371362708559174928518083 23234054902693948218369037998846599452866032192468 40143902699724440710206767117232436987249717376855 36222915595312580711590470064171487212320561962251 53661425895636768030312617466464534692663809752940 96586459930486041530542552966518300106447757425351 17596286388427152455691768496273029486357026418662 83482521083746986733544397519525982226988814389643 10121759653137508564231507756529890869545238898002 55441672479977676107316848218296858753037424135563 19718243574147181320484478081247147967824536276816 36099169567792360239808175356309716047822278120719 24329949600735941653992950580111496383100602620036 40125771281349644548101436520612777987835509035000 25962009298105048940597304299933085619698932668281 30180493427481209275248616189705998235120888728085 93876828016567410496732649793230240591964689011040 11506548864862586454104562372570630360720949263792 72263157736006182281706252785128510638569586089686 19156942995712818315720799344160277816889914906611 06846025038579281157013760312143938576928704231015 93246690506882546790676777827827506067487908935910 37669761244545383709642357818588783918654371805863 17431698396857060092492225545854182883400158574749 44094822718624630146993966548028940720920364951645 05317920011837528071152749341548467404930575343568 51202753169210308133272063714790965372801760581785 76426299480956428287928310362373497295188344821569 24790857399648864716589724882104207277832159252040 04739144462807296601758813825467704158115967866886 81322442146563721185939433594428768763162512320403 57902952109278031055996615090125588845280038799978 52776308253527608242862332663587938931441684570780 87784690907481197749949763041964203792719699416289 85263929924520995900375906824725658473794200408745 78140592358894676991109352113251441140341144181411 13030287734365911461163817110653075709888831619375 60885846956696881292526930021061158510755117144714 27286742791932392041490835522658389727500246585354 18364709010838708124716455349457777527713024860284 14495724829451973266650328005749073496728293515201 84567410317422956008199766383662980247167608160527 64452599355305357586550176593162392599033228339993 67542486708515218393658571915436668072522871258367 21199576705514962378372835334460644973335663070908 69711472484393044867664533224310804249595293310913 66846075453000905692621828113101049810547118717101 09498930911100568780023562460833934605147613781324 32182392309212713145307872391936107520633983398816 81017925636214126797790007915322393392432903038829 87428610875842000000000000000000000000000000000000 000000000000000000000000000000000000 52584720288108830725105101030540598131700091744324 70084608895728203669170494524618531343686042090121 76256147094954262811579772662434474355070783370075 12256051222796764424932312813736200399312632931472 52472784452199553448430672457564303844823295738347 25116996848440674152617072878793951530792818094999 32667850693300598457685353964472804032964688789556 86343368572893698091210402060450020459843289766433 98727251898007337153162756914776989525993138649186 01890852826198093680248578446370401027095681290558 90417815272251804468868732239909632453069212681330 52621803900461120646493473978238467502732870448663 38696738033255435055444376847753947394563648281153 15541115956943476378121196601313090133909355334139 59237178415368225925623445796917895057456000885492 19937660427303124105061458372639631033472445757438 80404558167395877885064438759679759276744543655421 88427270465412036599578773116358023239903304819825 99219693395226934405683123054147477535952687178248 10059425934814228543536888246961688241676328714853 12051910199754268165641247339239792004715303110408 84382644787870877228171398504820342479149505841259 25190878557359984835875428287989540796610831570316 86986188020764426201793094061389268009678687318083 01647976871675747653760593845926011891523488058966 36991699916705027908083510844125181457510579693046 91831678119551363602824333723838683437933811345861 18013480729934933535262655922600452173546421557486 90718119178375398329255894973198360022583059308445 68054068087310218391714371054162808544364775101689 95398003208231457214749025738352465406686277522788 95916131337664932417881136909490270561063196039747 26670654199820743817832698968891431208369993810643 71064686071853213741672596177982632427303901762365 20239767071992544317232243205204075619503416874683 87174724450624817896352102943245853460666466093253 62202842277193377572271943843756973403245339571101 27919614224914071333453674125076017508334944266403 09138643416015433463019340632975766114311130112813 92888677281503585660810634163153010272782602691117 46214401188288281552270336914012269226405776889506 56464188522011941553978840403982762259693872715134 19470491452060632003350757295392008282419340996007 50027657018954371544003337977167018345884001104257 13109853118809857125533241895389688256647625331763 42788311422983208291269593524809968422845894014899 18006858253574360890551630388880549261054063816724 88027010553394348496694729626838404114383815452410 66000229565822939907303569553934558296855456636188 29067154865375199878812041252987705705361715594356 69819660041750004984170519149753127944831492470270 22081078560234155640481038596832618016360561437234 21147225853136863587163797491619211916721104701356 12126023796167056245827471476039623607016631193338 10715397520237758860182962656505858161692710058899 31055089130487104198321118783679704545607175601745 33905797246509270774204794245982939170638252568337 36895715049937428484131119538907967197635486332234 69394028485706728996150447487415361140697028728116 22741349440917388208508819422426756019727473707406 73534224807945243515252327990683237457991513745743 59824308139173320670730732863144393268076006598739 97184057737057712155285367756592566486987608218665 02641235756298015129751579949179961527019321649192 24437846216336990100176913885644257820750963531971 49909876274968204245668984515387858003924307028488 17363162188730061133892162307857591687212139765181 62896936224652020458998986110176301979475490047082 94022127571657740962206008343984246468432787118954 22462838933657682460415996203750627827975088927428 43906515968129855408453852852423950549744424974401 97067745651965867938527520833147133418182243668758 09917993364567932443263643869902711545650392246308 53790368376484482896932511838402466483372069862513 78094698959691448626925048770341405724307666318397 55746619833910229823243133507410697686965536432104 05405153573283514342918746069282810085897693304617 14299092566882196554467339269483523061334901170347 81120118471965323764401439160911677892484338187031 50090819337146588182241806871576092124691370049153 29563686827517872363463764432087833001142304742189 39919168993010086620470567470489419129128271187393 66188290747519968490377732805899512427071436586287 60428665363898642342785988197902578979344621822887 34224923423854583816068355038488174304749628906370 93064282447488603499071172803259435098041789411124 20527966662018054306428716994501968058437051767276 87448687145491438717555099824581425217007879783954 03682055040298214509599556165331669786429249314251 28863107671314872457217612357689995810700637711894 14281845165366701157482811832131662795000409635394 95874289967617991695309401201516080822296090814552 35699865289690076441953790737400412333309548869911 34964243765585117141428912376426191320888390766607 49132110293686791491441181857391201683139589789632 04746664024644578462073180518988098758905455293107 55711764969904220673484237822913798800911931952358 08385389987205770338301957361428504960773768753774 37987420535297301163498534865196648435902688401963 10091506885658252808971952462319896744536957010894 44346509136837498384744875408695266056694745598138 02442334039671587132228919186380402141973724858971 05521400411534889088919816003365500241418639414643 93206085594784810599973384758922712140943737778375 03479113836055872583620535826501539345934649727374 89804468651372577598454769612553524924673336040473 76486517739497552778276226498602376730824974836712 63371045014184767281137433133431868644961806465604 33001495646778342324634084882341188919629150628602 39075899115011229031077430884380097285935504897010 39158062679626478848083849173181988705625417430264 11056356833948225621449048084376357833442583177034 84924094256314700187963683886945414085442838224043 81083070949734843568083638016661833351595593722364 67358887048673647039601147125532910588925330994773 04775424860634864713080623633513399261538512490766 21125192695981307494069889610526361260391054748021 73294090571521017635606423287229851318279044744304 24009538440995624229624215451621985106386794632526 21037795009428146013286453984526102851705281634797 34354685562323080250367702726833246113612304542648 25849980732890230594175831374566312188844798548236 08246117697771945719665415428807048987596463198731 14574800035007023964450167073651764125681070849956 16879023111746836696948413078464964622812323603688 71676296519668273739667125598315501915833190200106 89057967563790159314535958997676533645440641132862 69455030638197233687242812504749385033209800533582 30622588805449446367946125625636963155339444584705 25483737068786892565731421624027933656540464617050 83649460740030648982244965650167158800015739731567 89342829920050674255313824206135095506121514733274 58076672295352734411654362428704528351384157611790 06728905013299812396633366505926421608850481901574 87180314630060464378702112360472182983418507919559 68807184008612483423812623780554594615962514653276 27083087561087099386017709760555326176800152781179 58424819078229517397115318856278934706816196313423 26032123690826462430278706746415517845417890847212 70839452664174598297710485573246159499855395850588 57391699988929277708952067038843279324559915224168 2

The Unreasoner
03-29-2016, 07:46 PM
So I don't know if this really belongs here, but I have a question...

You know those pop rock things that have some kind of firework stuff wrapped in tissue paper? Well there's another one that I got once in Hawaii that's similar, but its actually a solid blueish-purple pellet sold in a kind of pill container (like a plastic tray with little dips in it sealed with paper).

Does anyone know what's that's called?