SAT Solvers

SAT? No, not the scholastic test. Rather, this deals with Boolean satisfiability which is a hard problem. A comment of Moshe of ACM Communications motivated this post. He was at a workshop this year that looked at a couple of things. One was whether were new theoretical insights from practice of late. The other was a sampling of techniques that solves these types of problems, albeit by rule of thumb.

We earlier mentioned algorithms as having a firmer basis than heuristics. There are a lot of SAT approaches. Let's pause here for a couple of pointers: Understanding SAT solvers, Flow Control Analysis for SAT Solvers. We could find a lot more.

From his observing the state of the art at the workshop, Moshe says that the methods are mostly heuristic. We might say that there are two issues to consider. One is that the hardness of a problem relates to the difficulty of finding its solution in an effective (time, resource, money) manner. The other is that solutions, if found, can be verified quite easily (compared to the search).

What does this mean for truth engineering? Firstly, assessing truth is a hard problem, computationally. We know this. But, truth is hard in general, too. Efforts at determining truth need to be reasonably constrained, if possible.

So, it is nice that we see motivation to define and explore the efficacy of a solution approach. However, we must, too, remember that maintaining the truthful state is not a given. In some cases, the trouble related to maintenance may be even worse than the original determination.

Catch-22? Somewhat. But, not.

Remarks:   Modified: 05/30/2014

04/24/2014 -- For a recent discussion on the other SAT, see Rick's post (he mentions big data and analytics, thereof).

05/30/2014 -- The May CACM (Vol. 57, No. 5) had an interesting article title "Understanding the Empirical Hardness of NP-Complete Problems" in which the authors talk about helping resolve hardness, somewhat (taming the beast), via statistical means. Makes one almost thing that these issues are of no concern going forward (throw computational power at the problem). But, it cannot be as easy as that (to wit, at the end of the 18th century, the Illuminati was claiming that everything was known about physics - so everyone go home and twiddle your thumbs). As the authors say, has to do with whether you can get solutions and whether you can do so in a reasonable time. Yet, there is more (still to be characterized). If the spaces quake, solutions become more difficult. Say what? Yes, we'll be getting back to this.

Codecademy, again

Context: See Tru'eng anew, focus going forward, mathematics.

--

As we get technical, we'll have to look at coding, mathematics, and philosophy. For the first (coding), there is much to consider. The past week, I have looked at Codecademy's site, taken some of their lessons, and reacquainted myself with code (see first and second bullets, below). For the second (mathematics), I re-looked, yesterday, at a site dealing with mathematical physics. The site had posts about the authors recent finds (see third bullet, below).

For the last, see this Facebook (Philosophy matters) page, for now. I ran across this page while researching, after reading an article in Bloomsburg Businessweek about applying Heidegger to marketing of stuff. Well, truth will deal with business as much as with mathematics, science, and engineering. So, we will definitely be back to this.

- Coding - On this past Monday, I was looking at the read counts and saw that the Codecademy, at last post was in the most-read mix. Note that it had been written in September of 2012. Rather than post a comment on Facebook, I went to Linkedin and did several. Why Linkedin? My profile there talks about my experience with code over the past several decades. I have moved the comments from Linkedin to here; they follow: 02/24/2014 - I ran across codecademy.com in 2012. At the time, my interests were directed toward things other than code. If someone had asked me six years ago if that were possible (life without code - you see, I was buying into the code-based worldview - even though I knew that being was not subsumed therein), I would not have understood the question. Yes, one can live, nicely, without code, but ought we?. Then, today, I noticed that the post had been recently read, several times, so I looked again at the site. Hence this notice. 02/25/2014 - Started yesterday afternoon, off and on, going through Codecademy lessons. As of now, I have completed 48 of these. Which means coding up the example sufficiently to execute properly and to get by the watchdog that controls stepping to the next item. (see post Focus going forward)  02/26/2014 - Well, it isn't that the honeymoon is over, yet the glitter is gone. Sloughed through all sorts of errors, today, that the environment kept throwing at me (being long-time at this type of thing, was able to alter the situation properly in order to accomplish what I wanted). Ah, I miss the Lisp machine. While thinking of the Lisp machine fun, I recalled Prof Lucio Arteaga who worked with me on issues related to topology, category theory, and more. (see post Acknowledgements) As I was looking at Codecademy, I went through the process. The next bullet provides a snapshot of the activity.

- ... The image shows my profile at the Codecademy site. One steps through lessons for a language. Right now, it shows that I have completed HTML & CSS, jQuery, PHP, and YouTube API courses (hence, the badges). The first two were reviewed to catch up with what has been going on. As people talked when they bragged of going from static to dynamic pages, there is a lot of flexibility. And, one sees many sites related to things like buttons and such. Codecademy profile as of 03/02/2014 To discuss: This is fine as it can be fun. However, as I knew then, and everyone ought to know now, re-write (and the logic thereof) is a difficult problem with open issues. How is it that we have allowed this type of mess to be cast upon the world at large? The YouTube API course was interesting. Again, a couple of years ago, when Microsoft pushed people off the OfficeLive site (people had actually built their processes upon that MS offering), I did not think that MS was offering anything worth my time. So, I went to another provider. After looking at the "free" web site builders, I didn't find one that I liked. So, I hacked HTML using my early 2000 framework. Then, last year, I looked at Joomla, Concrete5, and others (see the ajswtlk.com site, as we will be changing that as an exercise). What I am considering now will be to use CSS mainly (so, thanks Codecademy). Notice that I'm in the process of looking at Python (was my favorite language after Lisp), Ruby on Rails, and Web Projects (mainly to see what people have done). Perhaps, after that I might try to do a class myself. I have been taking notes along the way. Notice, above, that I said that the glitter had left. Well, it can be tedious. You see, the courses have a watchdog that is not as intelligently designed as it ought to be. I have snaps of tricks that I had to do to get the thing to parse correctly in order to let me go on when I had things right, but the watchdog (course controller) could not see it. To wit, I have been hung on Ruby for several days not (32%) since the thing will not parse properly. I'll keep trying. If I get to 100% on everything else, I might have to contact the Codecademy folks. I will list some of the problems that I saw: racing/hung condition when trying to parse, improper refresh of their data structure (to wit, list where you were supposed to enter the line number in a blank field - to get it to parse, I reversed a couple of the numbers), ..., not handling delimiters properly (to wit, introducing a space - not necessary, in this case - urged the parser along).

- Imperatives Everyone ought to code something or other. Otherwise, we have the situation where wizards do the work and get too much freedom in the process. That is, people abdicate their responsibility. Or, they get addicted to whatever the wizards provide (alluding to the recent gaming pull and more). But, to be serious, the last post (Logic ... Reflections ...) mentioned discussions dealing with issues to which truth engineering needs (has) to pay attention. The main thing concerns the "fact" that our supposedly deterministic ways are not so. Computing (especially, the cloud) makes the problem even more of concern. Now, even if everyone does not code, they ought to be concerned about maturity (and, by inverse, immaturity). This week I read about some of the software engineering practices of JPL. In this case, it was the Mars program. The test, in this case, was the one-time use during the mission. A whole lot of upfront analysis and testing was necessary. Where is there any time for this type of thing with agile playing around? On the other hand, things seem to push out to the web in various states of incompleteness. Perhaps, the ease of a back-off (not done if the errors are minor, and the user can adapt) is the driver. Or, is it that we do not want to know the real costs, or to pay, for better solutions that are necessary for sustainability (of more than stuffing big pockets)?

Remarks:   Modified: 01/15/2015

03/03/2014 -- We need to relook at several things. Yes, like, bringing memes (and more) to the fore in the discussion. Mathematicians have their "ancestors," know about them (and their contributions), and honor them. What other field does that? My mathematical pedigree: Galileo Galilei (1585), Vincenzo Viviana (1642) Isaac Barrow (1652), Isaac Newton (1668), Roger Cotes (1706), Robert Smith (1715), Walter Taylor (1723), Steven Whisson (1742), Thomas Postlethwaite (1756), Thomas Jones (1782), Adam Sedgwick (1811), William Hopkins (1830), Arthur Cayley (1864), Andrew Russell Forsyth (1881),  Edmund Taylor Whittaker (1895), G.H. Hardy (), Edward Charles Titchmarsh (), Andrew P. Guinand (), Lucio Arteaga (1964), the blogger (). I took it back to 1585 since that would be co-temporal with those who were involved with the Great Migration to New England. Too, note that the ancestor is an adviser or mentor or tutor. This brings to mind that a meme'tic look at descendancy would consider the influence of step-child-ness. I have found many of these relationships.

03/07/2014 -- Like a lot of things on the web, this site is free. Given that, some think that leaves no right to comment or criticize. But, along with the free (which really is a subtle way to entangle) comes a total one-sided deal where changes are pushed upon users without much (or no) notice. Conform to (watch out for) the big elephant turning over in the bed is adage. Of course, the whole notion of incompleteness as it applies to computing is not understood, or downright ignored, by those who know better. In fact. many of the new billionaires can exalt in proving that they're smarter by having more money (my counsel would be for them to not think their brilliance outshines some very poor people - truth engineering will deal with that subject). ... Now, finally, the beef deals with the watchdog (supposedly couched as training overseer) function is idiotic in some cases. One of note. The console shows a printout just like the lesson wants. However, the watchdog says that it looks like there was not output. This type of thing is hard to skirt around whereas parser types of things can be tweaked enough for them to be happy.  --- Late note, I found a way around the watchdog's errancy. Will report back on this later.

03/19/2014 -- Update, on Fedaerated.

05/27/2914 -- Codecademy has a nice Javascript glossary with examples.

06/23/2014 -- Example of true cost being ignored: Phone app in eight hours.

01/05/2015 -- Tru'eng, anew. This post is one of the most popular, of late, which raises some interesting questions. But, code as the focus? We have this from Tegmark: Consciousness as a state of matter.

01/15/2015 -- I will be getting back to their site, soon. Perhaps, I can use javascript to have some demos about this topic which is a series that will establish the basis and extensions for a fair and technical economic framework (motivation? sustainability). We are going to go back to some simple and come forward to the modern, complicated economy. Why? My long chain of ancestors (inherited via Prof. Lucio Arteaga) is one motivation.

Logic, Probability, Reflection, and more

The items in the subject of the post came from a meeting that was reported by John Baez. There are a couple of things to note, briefly.

Firstly, John Baez has reported his "This Week's Finds in Mathematical Physics" since the early 1990s. And, he kept his format consistent until a couple of years ago. His last post under the old site was on April 11, 2012. I was not a regular reader, but I did appreciate the site (used it as an example of how one could have deep content on the web without the frills) enough to visit it often.

The Week's Finds posts have been subsumed under a blog that was started in 2010, called Azimuth. If one reviews some of the posts, one can get the sense that graphics are a big help to good presentation. And, improvements in handling graphics are remarkable.

Secondly, as we see with the subject of the post, the meeting dealt with issues related artificial intelligence which has become (will continue to be) integral to advanced methods. John reports that the two main themes were Scientific Induction in Mathematics and Lob's Theorem (Cartoon Guide).

Of interest, too, is that the place of the meeting was called the Singularity Institute (see singularity). It now has the name of Machine Intelligence Research Institute. We have used the term in another context and will continue that discussion.

Remarks:   Modified: 03/23/2014

03/23/2014 -- SAT solvers as an example of large class of heuristics.