Jump to content

Why not add more variables to obtain an invertible matrix, in order to solve the SAT problem in polynomial time?


Z.10.46

Recommended Posts

 

Hello,

 

In short, we can transform the SAT problem into AX=1 withX a vector and 1 the vector of 1, but the determinant A is often zero, so A^-1 does not exist.

However, assuming that since I have the form of the A determinant, I could construct a polynomial-time algorithm where I add more variables to avoid having a zero determinant, I could then find 𝐴′^-1, and the solution would be in polynomial time to find X'X in X.

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.