Jump to content

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

Featured Replies

 

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.

Please sign in to comment

You will be able to leave a comment after signing in

Sign In Now

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.

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.