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
Brenda wants to finish her presentation with a summary slide . She wants three key messages to appear on each of the photo clips
Sav [38]

Brenda can first include an image and then include text. Lastly she can just provide an enhanced effect to the text to appear one by one each photo clip.

4 0
3 years ago
Read 2 more answers
How can you have a safe browser experience
goldfiish [28.3K]

Most likely the answer is to delete cookies, as it cuts down on the amount of tracking sites can do to you.

6 0
3 years ago
Which of the following is a true statement about psychological tests administered by computers? computers make standardization e
Hitman42 [59]
Thank you for posting your question here at brainly. I hope the answer will help you. Feel free to ask more questions.
the true statement about psychological tests administered by computers is 
<span>most people find computerized tests to be difficult to understand. </span>
7 0
3 years ago
Write a statement to create a Google Guava Multimap instance which contains student ids as keys and the associated values are st
Sergeu [11.5K]

Answer: provided in the explanation section

Explanation:

Note: take note for indentation so as to prevent error.

So we import com.google.common.collect.Multimap;

import java.util.Collection;

import java.util.Map;

class Main {

   public static void main(String[] args) {

       // key as studentId and List of Profile as value.

       Multimap<String,Profile> multimap = ArrayListMultimap.create();

       multimap.put("id1", new ExamProfile("examStudentId1"));

       multimap.put("id1", new ELearningProfile("userId1"));

       multimap.put("id2", new ExamProfile("examStudentId2"));

       multimap.put("id2", new ELearningProfile("userId2"));

       // print the data now.

       for (Map.Entry<String, Collection<Profile>> entry : multimap.entrySet()) {

           String key = entry.getKey();

           Collection<String> value =  multimap.get(key);

           System.out.println(key + ":" + value);

       }

   }

}

// assuming String as the studentId.

// assuming Profile as the interface. And Profile can multiple implementations that would be

// specific to student.

interface Profile {

}

class ExamProfile implements Profile {

   private String examStudentId;

   public ExamProfile(String examStudentId) {

       this.examStudentId = examStudentId;

   }

}

class ELearningProfile implements Profile {

   private String userId;

   public ELearningProfile(String userId) {

       this.userId = userId;

   }

}

This code is able to iterate through all entries in the Google Guava multimap and display all the students name in the associated students profile.

8 0
3 years ago
Each time an end user clicks a hyperlink, the browser generates a(n) _____ page request that is sent to the designated web serve
irina1246 [14]

Answer:

HTTP GET

Explanation:

The Hypertext Transfer Protocol (HTTP) is designed to enable communications between clients and servers and it uses the GET method to request data from the specified resource using the TCP/IP Internet protocol.

4 0
3 years ago
Other questions:
  • Carmina wants to move a paragraph to the right margin of the document she is working in. She moves her cursor to
    8·2 answers
  • Paul is the web page designer for his company. Paul’s boss tells him that customers have been complaining that it is difficult t
    8·2 answers
  • QUESTION : John travels a lot and he needs to access his documents and services on the go. Which of these technologies allows hi
    15·1 answer
  • What is an example of a good URL?
    7·2 answers
  • Which information is considered free for use?
    9·2 answers
  • Which of the following is NOT a strength of monetary policy?
    15·1 answer
  • Is spin to win paying or is a scam app​
    6·2 answers
  • Which types of file formats are the best choice for files that may need to be edited later?
    14·1 answer
  • How do i mark brainliest?
    6·2 answers
  • Technology __________ guides how frequently technical systems are updated, and how technical updates are approved and funded.
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!