1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
viva [34]
3 years ago
7

Under the assumption that there exists an unknown Turing machine encodableinc1bits that decides3-SATis inO(n10) time, give imple

mentation details for a Turing Machine M that decides 3-SAT in O(n10000) time.
Computers and Technology
1 answer:
zmey [24]3 years ago
7 0

Answer:

3. (9 points) The goal of this problem is to show that our formal definitions of P and NP imply that P = NP cannot have a non-constructive proof. Throughout this problem we assume a consistent, binary, encoding of both Turing machines and 3-SAT instances. Note that the complexities are intentionally not tight to address potential overheads from scan- ning the tape linearly in order to look for certain symbols. (a) (3 points) Show that for any constant cı, there is a constant c2 such that if Mi is a Turing machine encoded by at most bits that correctly decides 3-SAT in O(n10) time (aka. 3-SAT E TIME(n10), then there is a Turing machine M, encoded by at most most c2 bits that runs in O(n100) time such that if the 3-SAT instance has a satisfying assignment, M, accepts and writes a satisfying assignment at the end of the tape. (b) (3 points) Let M ...Mbe Turing machines show that the language {(k, M... Mk,t,w) | w is an instance of 3-SAT and one of M, writes a satisfying assignment to w in at most t steps can be decided by a Turing machine in (k2107 10) time. (c) (3 points) Under the assumption that there exists an unknown Turing machine encodable in c bits that decides 3-SAT is in O(n10) time, give implementation details for a Turing Machine M that decides 3-SAT in O(n10000) time. Hint: the constant factor in the big-O is able to hide any function related ci and c2, which independent of input sizes, and thus constants.

Explanation:

3. (9 points) The goal of this problem is to show that our formal definitions of P and NP imply that P = NP cannot have a non-constructive proof. Throughout this problem we assume a consistent, binary, encoding of both Turing machines and 3-SAT instances. Note that the complexities are intentionally not tight to address potential overheads from scan- ning the tape linearly in order to look for certain symbols. (a) (3 points) Show that for any constant cı, there is a constant c2 such that if Mi is a Turing machine encoded by at most bits that correctly decides 3-SAT in O(n10) time (aka. 3-SAT E TIME(n10), then there is a Turing machine M, encoded by at most most c2 bits that runs in O(n100) time such that if the 3-SAT instance has a satisfying assignment, M, accepts and writes a satisfying assignment at the end of the tape. (b) (3 points) Let M ...Mbe Turing machines show that the language {(k, M... Mk,t,w) | w is an instance of 3-SAT and one of M, writes a satisfying assignment to w in at most t steps can be decided by a Turing machine in (k2107 10) time. (c) (3 points) Under the assumption that there exists an unknown Turing machine encodable in c bits that decides 3-SAT is in O(n10) time, give implementation details for a Turing Machine M that decides 3-SAT in O(n10000) time. Hint: the constant factor in the big-O is able to hide any function related ci and c2, which independent of input sizes, and thus constants.

You might be interested in
What's the answer to this​
yarga [219]

Answer:

S

Explanation:

The index operator will address individual characters in the string.

5 0
3 years ago
Which of the following Python methods in scipy.stats submodule returns the P-value for performing a hypothesis test for the sign
ipn [44]

Answer:

Option B is the correct answer for the following question.

Explanation:

The following option is true because the pearsonr from scipy module is the method of the Python Programming Language in the submodule i.e., "scipy.stats" which print or return P-value for operating the hypothesis test for the value of correlation coefficient. So, that's why the following option is correct.

7 0
3 years ago
Help ME! Will Mark BRAINLIEST! Its Engineering!
Anettt [7]
What is it about ? And what you need help on
5 0
3 years ago
Locker doors There are n lockers in a hallway, numbered sequentially from 1 to n. Initially, all the locker doors are closed. Yo
kow [346]

Answer:

// here is code in C++

#include <bits/stdc++.h>

using namespace std;

// main function

int main()

{

   // variables

   int n,no_open=0;

   cout<<"enter the number of lockers:";

   // read the number of lockers

   cin>>n;

   // initialize all lockers with 0, 0 for locked and 1 for open

   int lock[n]={};

   // toggle the locks

   // in each pass toggle every ith lock

   // if open close it and vice versa

   for(int i=1;i<=n;i++)

   {

       for(int a=0;a<n;a++)

       {

           if((a+1)%i==0)

           {

               if(lock[a]==0)

               lock[a]=1;

               else if(lock[a]==1)

               lock[a]=0;

           }

       }

   }

   cout<<"After last pass status of all locks:"<<endl;

   // print the status of all locks

   for(int x=0;x<n;x++)

   {

       if(lock[x]==0)

       {

           cout<<"lock "<<x+1<<" is close."<<endl;

       }

       else if(lock[x]==1)

       {

           cout<<"lock "<<x+1<<" is open."<<endl;

           // count the open locks

           no_open++;

       }

   }

   // print the open locks

   cout<<"total open locks are :"<<no_open<<endl;

return 0;

}

Explanation:

First read the number of lockers from user.Create an array of size n, and make all the locks closed.Then run a for loop to toggle locks.In pass i, toggle every ith lock.If lock is open then close it and vice versa.After the last pass print the status of each lock and print count of open locks.

Output:

enter the number of lockers:9

After last pass status of all locks:

lock 1 is open.

lock 2 is close.

lock 3 is close.

lock 4 is open.

lock 5 is close.

lock 6 is close.

lock 7 is close.

lock 8 is close.

lock 9 is open.

total open locks are :3

5 0
3 years ago
In which two places are a keyboard usually held on a laptop?
Margarita [4]

Answer:

Bottom of the case

Through a connector

Explanation:

Regularly we must see the bottom of the case to remove some screws, and then move the keyboard, but first, you have to remove a connector.

The keyboards have evolved from windows and IMB built their own keyboards for desktop, and now we have digital keyboards, and replace a keyboard in a laptop can change for the model or the size.

6 0
3 years ago
Other questions:
  • Ms Access is spreadsheet software.True or false​
    9·2 answers
  • How can users create a shortcut to favorite websites and store them in their browser?
    8·2 answers
  • Most users find settings between ____ to be the most convenient option for how long the computer sits idle before the screen sav
    14·1 answer
  • Amazon Web Services (AWS): Group of answer choices a) forms a majority percentage of Amazon's overall revenue. b) was introduced
    15·1 answer
  • I have six nuts and six bolts. Exactly one nut goes with each bolt. The nuts are all different sizes, but it’s hard to compare t
    12·1 answer
  • "Write an iterative function iterPower(base, exp) that calculates the exponential baseexp by simply using successive multiplicat
    10·1 answer
  • How can the function anotherFunc2 change the contents of the second element of t?
    5·1 answer
  • Raul needs to ensure that when users enter an order into the tblOrders, the shipping date is at least two days after
    9·2 answers
  • Which of the following statements is FALSE?
    5·1 answer
  • Greenpeace used "Mister Splashy Pants" to:
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!