Groups | Search | Server Info | Login | Register

Groups > sci.logic > #255202

Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines

Show all headers | View raw

On Monday, July 3, 2023 at 4:11:16 PM UTC-4, Daniel Pehoushek wrote:
> On Monday, July 3, 2023 at 1:20:57 PM UTC-4, Rich D wrote: 
> > On June 24, Daniel Pehoushek wrote: 
> > > regular graph coloring is np-complete. 
> > > i have solved millions of them. 
> > > three coloring fifth degree 250 vertices (500 boolean variables) 
> > > thats 625 edges. 
> > > five coloring uses 3 boolean variables to encode 5 colors. 
> > > 
> > > i solve all qbfs on these graph coloring formulas in sets of ten thousand. 
> > > as graph size grows, np-complete problems become exponentially difficult 
> > > but are solvable for modest sizes. 
> > > 
> > > class allqbfs solves all qbfs given all models. 
> > > the output is brief monotone and conjunctive. 
> > > 
> > > the traveling salesman problem is np-hard but i do not mess with it. 
> > What about Hamiltonian circuits? 
> > 
> > -- 
> > Rich
> hamiltonian circuits are np-complete and counting them is #P-complete 
> so that is similar to graph coloring and boolean formulas 
> 
> i concentrated on solving general conjunctive normal boolean formulas with graph coloring as the random input in mass quantity 
> 
> i solve the whole boolean hierarchy including "all quantified boolean formulas" 
> and succeed on modest size (up to 250 vertices, 500 tough boolean variables) 
> 
> the output decides all qbfs and is a monotone cnf on n variables 
> 
> the key feature to the pspace solution is zero negations in the output of universal truth 
> 
> so avoid negation to be good at thought 
> daniel2380+++ summary of thirty years of research 
> 
> the lifes work is 1000 equations in c++ 
> with 50 line core of class allqbfs for solving all of pspace
once upon a time i gave a talk at stanford university
it was about counting hamiltonians in a regular graph
i had a small tree width graph of 25,000 vertices with 2^2000 or so hamiltonian circuits
the group was the aflb algorithms for lunch bunch

avoid negation
daniel2380+++
and be well

Back to sci.logic | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Rich D <rdelaney2001@gmail.com> - 2023-06-22 14:38 -0700
  Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-06-22 15:25 -0700
    Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Rich D <rdelaney2001@gmail.com> - 2023-06-24 13:04 -0700
      Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-06-24 14:14 -0700
        Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Rich D <rdelaney2001@gmail.com> - 2023-06-26 10:22 -0700
          Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-06-26 15:27 -0700
            Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-06-27 03:00 -0700
              Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-06-27 07:54 -0700
                Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-06-28 12:44 -0700
        Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Rich D <rdelaney2001@gmail.com> - 2023-07-03 10:20 -0700
          Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-07-03 13:11 -0700
            Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-07-03 13:24 -0700
              Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-07-03 14:51 -0700
                Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-07-03 15:23 -0700
              Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Rich D <rdelaney2001@gmail.com> - 2023-07-03 15:57 -0700
                Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-07-03 20:44 -0700
                Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-07-12 17:06 -0700
                Re: NP Pspace #P #Q Qspace equality theory for modest sizes in 1000 lines Daniel Pehoushek <pehoushek1@gmail.com> - 2023-07-20 06:01 -0700

csiph-web