Jump to content

P=NP almost hooked


angela weiss

Recommended Posts

 I've  submited a paper that was a result of a frustreted attept to show that P=NP. I found a fatal flaw but mended the pieces. The result is a draft Iǘe submited and some exemples in my page. Not a "proof", but a weaking of 3.SAT. Maybe there are classes of formulas we can untangle.

I am seeking for advices better than "give up" for it is not real Science nor Philosofy. 

Thanks for the hints,

angela

https://www.ime.usp.br/~weiss/

Link to comment
Share on other sites

I already have a polynomial time algorithm for k-Sat in Java . I don't have a phd and can't publish it in a formal journal as a result. So what is in it for me to help you? I'm sure nobody will solve it until I am in a position to publish anyway.

Your proof is wrong by the way.

Link to comment
Share on other sites

Hello Dear,

I think that you must publish it. Try SAT-live, http://www.satlive.org/

Maybe you are speaking Trumpsh, a new language that does not allow rational arguing. ;can you read my draft? Do you have the skil for it? y background is Math but it is not a cumbersome paper.

Give me, please, a more adult answer,

best

/\/

/\/(angela)

Link to comment
Share on other sites

 

Quote

 

Do you have the skil for it? y background is Math but it is not a cumbersome paper.

Give me, please, a more adult answer,

 

I can obviously read your paper and it is wrong. You asked for a hint and I gave you one. Here's another you can solve it in O(n^2) or less with parallelization. I feel it would be better to write it as an academic paper with references. But I am awful at writing papers and let's face it "Give me,  a more adult answer" will be exactly the kind of annoyance I can expect if I publish. There are people with phds who haven't solved it for years I doubt they will look favourably on somebody who doesn't have one (There is quora questions on this exact thing)

 

Link to comment
Share on other sites

Hmm I would like to use my answer for my phd thesis. I suppose there isn't much harm in telling.

 

A

B

C

D

E

F

AC

AD

AE

AF

BC

BD

BE

BF

CE

CF

DE

DF

ACE

ACF

ADE

ADF

BCE,

BCF

BDE

BDF

0

F

T

F

T

F

T

F

T

F

T

T

T

T

T

F

T

T

T

F

T

T

T

T

T

T

T

1

F

T

F

T

T

F

F

T

T

F

T

T

T

T

T

F

T

T

T

F

T

T

T

T

T

T

2

F

T

T

F

F

T

T

F

F

T

T

T

T

T

T

T

F

T

T

T

F

T

T

T

T

T

3

F

T

T

F

T

F

T

F

T

F

T

T

T

T

T

T

T

F

T

T

T

F

T

T

T

T

4

T

F

F

T

F

T

T

T

T

T

F

T

F

T

F

T

T

T

T

T

T

T

F

T

T

T

5

T

F

F

T

T

F

T

T

T

T

F

T

T

F

T

F

T

T

T

T

T

T

T

F

T

T

6

T

F

T

F

F

T

T

T

T

T

T

F

F

T

T

T

F

T

T

T

T

T

T

T

F

T

7

T

F

T

F

T

F

T

T

T

T

T

F

T

F

T

T

T

F

T

T

T

T

T

T

T

F

 

See the table this is all the possible things that could be wrong in 3 Sat. I wrote a generator to create the above table. e.g. Solver solver = new Solver. I assign it to a static custom HashMap() which has a get method where I pass clause a and clause b. It then checks the hashmap for the False values.

It is easy to see that what it returns is a boolean array with 8 terms. e.g. for A it is FFFFTTTT and so on.

The generator is only used in the constructor so it has no effect on the runtime in the worst case. 

We call the solver with an array of clauses and then iterate over it like so.

boolean[] satisfiable = (TTTTTTTT)
for (int i =0; i <array.length; i++){

  for(int j=1; j<array.length; j++){
	//get value from the hashmap
	//join to the array
	//eg. a=FFFFTTTT
  }
  
  //check if satisfiable is FALSE 
  // return

  // else reset the value
  satisfiable = (TTTTTTTT)

}

It is easy to see that this is O(n^2) in the worst case. It is similar enough to bubblesort that it could be even faster.

I can easily extend the array to K-Sat by increasing the size of the Custom HashMap generator. To generate the table from above I pass in

String[] array = {"a","b","c","d","e","f"};
char[] charArray = {'a','b','c','d','e','f'};

So I can extend it by adding g,h,i,j,k etc.

Link to comment
Share on other sites

I am joking, I cannot afford to go to college because my family is poor. I also work long hours most days so I don't have time to write an academic paper. But I have read basically everybody else's notes on P vs NP.

Look at the table I provided again what happens if I replace A-F with the numbers 0-6? For P vs NP we are asked to create a Turing machine with a deterministic finite automaton. A DFA just maps symbols to other symbols. Once we have the table from before everything else is just how to we convert the input into the format of the table which is basic maths.

Say I give you the clause 123, 167, 253 I need that in the form 0-6 so what do I take away to get it into that format? The exact number provided right? 

Now when I match that against another clause say 145,169,267 well then I do basic subtraction (145-123=22, 169-167=2, 253-267=-14). We can easily see that 22 is not between 0 and 6 so the clause has no bearing on the satisfiability of the initial clause.

If the number after subtraction is between 0 - 6 then we follow the table and transition to a state where we save the answer to the 8 bit memory and check if it is unsatisfiable. The for loop is basically instructions about how to move the Turing Machine's read head. In my case I am using 2 read heads.

An actual proof of P vs NP would have all the necessary transition tables and circuit diagrams to make that work. Simply having a working java class isn't sufficient.

 

Link to comment
Share on other sites

  • 2 weeks later...

Fate is a strange dice that we do not control. We jump and try our best.

I was born very poor. A family of survivors from the Second World War purge, not a Jew, nor a Kossac, not a Gipsy but part of them, só, no sides to shelter my grand parents. I was borm very poor and remeber starving. Brasil is not for amateurs! On the other side, the college is for free and you can get food and some clothes, só, I could attend the university amongst very rich kids. Do not know how but my grades very high enough to be there. It was a game, like jumping a circle of fire. Maybe I was able to jump but, after some jumps, there was nothing but stress, poverity and decepcion.

I am not telling a personal history as if it were a glorious fight. I saw fights in my place. Native fight against miners, againt diseases. I saw poor girls fighting against misery and winning all the odds in an “male world”.

I like Carlos Castañeda books. Once I was told he is totally fake but I like Don juan most of all and Don Juan says that a warrior must grab the 1mm³ of chances he/she got. I am very pragmatic. I do not mind my role in that teather. I am going to do my best and extract the fully joy of that act.

I believe we are very talented and able to do the best face to the rules of the game we have to play I know people that cannot be that clever. I know people that complain the husband they choose (there is no arranged matrimonies im my place for 200 years!), they complain the age, no matter how old are they, the lack of courage or the lack opportunities, spite you spare them the best piece of that play.

You are a warrior and I sense that. Just wanted to say that I know you did the best and grabbed all the chances.

Best

/\/

/\/

Link to comment
Share on other sites

  • 4 weeks later...
On 9/9/2020 at 4:54 PM, angela weiss said:

for it is not real Science nor Philosofy

Philosophy in form of naturphilosophy is more "real Science" than speculative mathematics 

I believe that the very terms in which this problem is formulated are incorrect, if not stupid. They take a calculation step without determining the complexity of the step itself, that is, (count the universe) + (count the universe) this is a simple calculation, of 2 steps

On 9/22/2020 at 3:57 PM, angela weiss said:

Kossac

What is it? Cossack?

where did you get that they "purged" the Cossacks?

Edited by molbol2000
Link to comment
Share on other sites

Oh, Dear, do not infer "they (who?) purged the Cossaks from what I said.My sentence has no double meaning or many consequences. It is just a personal report. My people fled to Brazil. Only a personal report and I believe that History  is a collection of personal relats and not writin using a single case.

I believe that Math is a branch of Philosophy. My personal believe. Applied Mathematics is another piece of this game. I never sowed this field.

Best,

/\/

/\/

Link to comment
Share on other sites

Quote

I was born very poor. A family of survivors from the Second World War purge, not a Jew, nor a Kossac, not a Gipsy but part of them, só, no sides to shelter my grand parents. I was borm very poor and remeber starving.

Okay this went weird fast. Look this is the code I have. It is more of a proof of concept than anything at the moment and is way messier than I would like since I don't really have time to look at it after work. As I said instead of a DPLL algorithm which randomly assigns values to literals and can take exponential time. I create a custom hashmap that works like a template and as a result can run in n^2 time or less while still getting a correct result.

https://github.com/davidmather/3SatSolver

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.