4. After graduating from the University of Michigan, you have decided to teach a computer science...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
4. After graduating from the University of Michigan, you have decided to teach a computer science course of your own. You create for your students some projects to complete, and now you want to write a program that will allow you to efficiently check if a student's code wrong in any way. In order to ensure your efforts are not wasted, you decide to use your 376 knowledge and construct a proof that this is possible. You come up with the following language and proof: LAUTOGRADER = {(Prog.cpp) : Prog.cpp is a C++ program that fails at least one test case out of T = t₁, t2,. , tn 2} ..." What is wrong with the following (faulty) "proof" that LAUTOGRADER E NP? "Proof". Define verifier V((Prog.cpp), (ti, k)): (a) Verify that t; is a test case in T. (b) Run Prog.cpp on test case ti for up to k steps. (c) If Prog.cpp returns false (i.e. it fails) within these k steps, accept; otherwise, reject. If (Prog.cpp) LAUTOGRADER, then Prog.cpp must fail on some test case t; after some finite number of steps k, which means that V((Prog.cpp), (ti, k)) will accept. And if (Prog.cpp) #LAUTOGRADER, then V will reject no matter what certificate (tį, k) is provided. Therefore, V is an efficient verifier for LAUTOGRADER, SO LAUTOGRADER E NP. 4. After graduating from the University of Michigan, you have decided to teach a computer science course of your own. You create for your students some projects to complete, and now you want to write a program that will allow you to efficiently check if a student's code wrong in any way. In order to ensure your efforts are not wasted, you decide to use your 376 knowledge and construct a proof that this is possible. You come up with the following language and proof: LAUTOGRADER = {(Prog.cpp) : Prog.cpp is a C++ program that fails at least one test case out of T = t₁, t2,. , tn 2} ..." What is wrong with the following (faulty) "proof" that LAUTOGRADER E NP? "Proof". Define verifier V((Prog.cpp), (ti, k)): (a) Verify that t; is a test case in T. (b) Run Prog.cpp on test case ti for up to k steps. (c) If Prog.cpp returns false (i.e. it fails) within these k steps, accept; otherwise, reject. If (Prog.cpp) LAUTOGRADER, then Prog.cpp must fail on some test case t; after some finite number of steps k, which means that V((Prog.cpp), (ti, k)) will accept. And if (Prog.cpp) #LAUTOGRADER, then V will reject no matter what certificate (tį, k) is provided. Therefore, V is an efficient verifier for LAUTOGRADER, SO LAUTOGRADER E NP.
Expert Answer:
Answer rating: 100% (QA)
The faulty proof that Ltext AUTOGRADER in NP is incorrect because it overl... View the full answer
Related Book For
Project Management The Managerial Process
ISBN: 9781260570434
8th Edition
Authors: Eric W Larson, Clifford F. Gray
Posted Date:
Students also viewed these programming questions
-
Dickens, Kristen, is enrolled as a doctoral student in the Counselor Education at the University of New Orleans. She is a registered counselor intern in the state of Louisiana and works at a...
-
In ancient civilizations, it was a common practice to open ones home to travelers who needed a place to sleep. This prompted the sharing of news, stories, and information. Couchsurfing International,...
-
What is the type of the expressions computed on these two lines? 4 > 5 print (4>5)
-
Reconsider Prob. 579. Using EES (or other) software, investigate the effect of the mass flow rate of the cold stream of R-134a on the temperature and the quality of the exit stream. Let the ratio of...
-
Even though metal is a good conductor, frost can be seen on parked cars in the early morning even when the air temperature is above freezing. Provide an explanation.
-
Using the variance data for Menounos Manufacturing Co., prepare an income statement through gross profit for the year ended December 31, 20Y6. Assume the company sold 3,000 units at $100 per unit.
-
1. Sheldon Cooper and Amy Farrah live in Pasadena, California; have as a new investment goal to create a college fund for their newborn daughter. They estimate that they will need $200,000 in 18...
-
The example may be a sales tax or income tax proposal at any level of government. In your initial post, explain the revenue proposal, and evaluate it for equity, adequacy of revenue generation,...
-
As the bookkeeper of Phil?s Plowing, you have been asked to complete the entire accounting cycle for Phil from the following information. Use the following chart of accounts. 1. Snow supplies on...
-
Consider an Automatic Teller Machine (ATM) . The following are provided for checking and savings accounts: Begin Transaction (with Card/PIN) Balance Enquiry Deposit Withdrawal 1) Identify ten...
-
Tazza is analysing the possible acquisition of Bichiery. Neither firm has debt. The forecasts of Tazza show that the purchases would increase its annual after-tax cash flow by 1.3 million...
-
The Dybvig Corporations equity has a beta of 1.3. If the riskfree rate is 4.5 per cent and the expected return on the market is 12 per cent, what is Dybvigs cost of equity capital?
-
In the previous problem, suppose you want only 400 total in dividends the first year. What will your homemade dividend be in 2 years? Data from Previous problem You own 2,000 shares of equity in...
-
NPV is just a tool and as with any tool, it can be dangerous in the wrong hands. (a) Discuss this statement. In what way do sensitivity analysis, break-even analysis and scenario analysis improve...
-
Advance plc is trying to determine its cost of debt. The firm has a debt issue outstanding with 7 years to maturity that is quoted at 92 per cent of face value. The issue makes semi-annual payments...
-
Teal Corporation issued 510 shares of $100 par value preferred stock for $57,300. Prepare Teal's journal entry. (Credit account titles are automatically indented when amount is entered. Do not indent...
-
The following selected information was taken from Sun Valley Citys general fund statement of revenues, expenditures, and changes in fund balance for the year ended December 31, 2019: Revenues:...
-
Define a white elephant in project management. Provide a real-life example.
-
Garth Hudson was a 29-year-old graduate of Eastern State University (ESU) with a BS degree in management information systems. After graduation he worked for seven years at Bluegrass Systems in...
-
What options did Habitat for Humanity(H4H) use to complete the house so quickly?
-
Given your response to item 2, how would these measures be useful? What could they be used for? Turnover is costly for organizations. In addition to the direct costs of recruiting, hiring, and...
-
How does New Belgium introduce fun into the workplace? How does having fun keep employees engaged and enthusiastic about their work and the company? Kim Jordan and Jeff Lebesch, the husband and wife...
-
Visit the New Belgium Brewing Web site (www.newbelgium.com) to learn more about the company. The company has a strong culture that values environmental sustainability. Here are its core beliefs: We...
Study smarter with the SolutionInn App