art by =saintchase

Theoryland Resources

WoT Interview Search

Search the most comprehensive database of interviews and book signings from Robert Jordan, Brandon Sanderson and the rest of Team Jordan.

Wheel of Time News

An Hour With Harriet

2012-04-30: I had the great pleasure of speaking with Harriet McDougal Rigney about her life. She's an amazing talent and person and it will take you less than an hour to agree.

The Bell Tolls

2012-04-24: Some thoughts I had during JordanCon4 and the upcoming conclusion of "The Wheel of Time."

Theoryland Community

Members: 7652

Logged In (0):

Newest Members:johnroserking, petermorris, johnadanbvv, AndrewHB, jofwu, Salemcat1, Dhakatimesnews, amazingz, Sasooner, Hasib123,

Theoryland Tweets

Forums

Home | Chat | Old Forums(Yuku)


Go Back   Theoryland of the Wheel of Time Forums > THEORYLAND STEDDINGS > Non WoT Discussion
User Name
Password

Reply
 
Thread Tools Display Modes
  #1  
Old 12-14-2015, 07:43 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default STEM thread part II

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.
__________________
Exfeuck? Not quite...
Reply With Quote
  #2  
Old 12-15-2015, 01:11 AM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

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.
__________________
Exfeuck? Not quite...
Reply With Quote
  #3  
Old 12-15-2015, 02:28 AM
Nazbaque's Avatar
Nazbaque Nazbaque is offline
Hero of the Horn
 
Join Date: Jun 2008
Location: Turku, Finland
Posts: 3,492
Nazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond repute
Default

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.
__________________
Warder of Freya Sedai
First-brother of Cary Sedai
Great Lord of Fire
Lord Captain Commander of Singing Chipmunks
Master of Nazgul Kitchen
Reply With Quote
  #4  
Old 12-15-2015, 02:28 AM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

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.
__________________
Exfeuck? Not quite...
Reply With Quote
  #5  
Old 12-15-2015, 02:30 AM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

Quote:
Originally Posted by Nazbaque View Post
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.
__________________
Exfeuck? Not quite...
Reply With Quote
  #6  
Old 12-15-2015, 02:52 AM
Nazbaque's Avatar
Nazbaque Nazbaque is offline
Hero of the Horn
 
Join Date: Jun 2008
Location: Turku, Finland
Posts: 3,492
Nazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond reputeNazbaque has a reputation beyond repute
Default

Quote:
Originally Posted by The Unreasoner View Post
Exactly. The art of asking good questions is humanity's highest. It takes a great mind to use great tools.
Or a lucky guess.
__________________
Warder of Freya Sedai
First-brother of Cary Sedai
Great Lord of Fire
Lord Captain Commander of Singing Chipmunks
Master of Nazgul Kitchen
Reply With Quote
  #7  
Old 12-15-2015, 05:02 AM
GonzoTheGreat GonzoTheGreat is offline
Hero of the Horn
 
Join Date: Mar 2008
Posts: 15,842
GonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond repute
Default

Quote:
Originally Posted by The Unreasoner View Post
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.
__________________
I do not anticipate the invention of a working time machine in the foreseeable future.
Reply With Quote
  #8  
Old 12-15-2015, 07:18 AM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

Quote:
Originally Posted by GonzoTheGreat View Post
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.
__________________
Exfeuck? Not quite...
Reply With Quote
  #9  
Old 12-15-2015, 07:31 AM
GonzoTheGreat GonzoTheGreat is offline
Hero of the Horn
 
Join Date: Mar 2008
Posts: 15,842
GonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond repute
Default

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.
__________________
I do not anticipate the invention of a working time machine in the foreseeable future.
Reply With Quote
  #10  
Old 12-15-2015, 04:39 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

Quote:
Originally Posted by GonzoTheGreat View Post
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.
__________________
Exfeuck? Not quite...
Reply With Quote
  #11  
Old 12-15-2015, 04:56 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

Now let's revisit tattoos using Boolean arithmetic.

From the old thread:
Quote:
Originally Posted by The Unreasoner
(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'?
__________________
Exfeuck? Not quite...
Reply With Quote
  #12  
Old 12-15-2015, 05:21 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

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)
__________________
Exfeuck? Not quite...
Reply With Quote
  #13  
Old 12-15-2015, 05:34 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

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.
__________________
Exfeuck? Not quite...

Last edited by The Unreasoner; 12-15-2015 at 05:51 PM.
Reply With Quote
  #14  
Old 12-16-2015, 06:28 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

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.
__________________
Exfeuck? Not quite...
Reply With Quote
  #15  
Old 12-16-2015, 06:51 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

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.
__________________
Exfeuck? Not quite...
Reply With Quote
  #16  
Old 12-16-2015, 07:16 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

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"]
__________________
Exfeuck? Not quite...
Reply With Quote
  #17  
Old 12-17-2015, 05:09 AM
GonzoTheGreat GonzoTheGreat is offline
Hero of the Horn
 
Join Date: Mar 2008
Posts: 15,842
GonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond reputeGonzoTheGreat has a reputation beyond repute
Default

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 do not anticipate the invention of a working time machine in the foreseeable future.
Reply With Quote
  #18  
Old 12-17-2015, 01:07 PM
Daekyras's Avatar
Daekyras Daekyras is offline
Elder
 
Join Date: Nov 2009
Location: Ireland
Posts: 1,772
Daekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond reputeDaekyras has a reputation beyond repute
Default

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!
__________________
You know what is comparable to LotR? Dragonlance. -Toss the Dice

He just got carried away a bit this time, probably as a result of his marriage-gonzothegreat

Son of Nazbaque, Lord of Fire
Reply With Quote
  #19  
Old 12-17-2015, 08:53 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

Quote:
Originally Posted by GonzoTheGreat View Post
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.
__________________
Exfeuck? Not quite...

Last edited by The Unreasoner; 12-17-2015 at 09:05 PM.
Reply With Quote
  #20  
Old 12-18-2015, 05:40 PM
The Unreasoner's Avatar
The Unreasoner The Unreasoner is offline
Elder
 
Join Date: Mar 2011
Posts: 3,382
The Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond reputeThe Unreasoner has a reputation beyond repute
Default

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.
__________________
Exfeuck? Not quite...
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 06:01 PM.


Powered by vBulletin® Version 3.8.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.