Advanced Algorithms, End Term

May 2023 term, 3 Sept 2023, Set QPE1-S2

Quiz Space

MusicOpen the study music controls.

CalculatorOpen the calculatorLearning mode

Question 1

+3−0Single correctInstructions

Tap to zoom

Select one option

• A.

  Instance 1

• B.

  Instance 2

• C.

  Instance 3

• D.

  None of these

Show answer

Report

Report a problem

Sign in to report a problem with this question.

Clear Response

PreviousNext

Submit this paper?

You cannot change your answers after submitting.

Answered

0

Not answered

1

Marked for review

0

Answered & marked for review

0

Not visited

2

Keep goingSubmit paper

Instructions

The palette shows the status of every question. Pick a number to go straight to it.

Answered

0

Not answered

1

Marked for review

0

Answered & marked for review

0

Not visited

2

• Save & Next moves to the next question. Answers are saved as you go.
• Mark for Review & Next flags the question to come back to. A flagged answer still counts.
• Clear Response removes your answer to the question on screen.
• The ← and → keys move to the previous and next question.

Figure from the original question paper Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? True or false?\ It is possible that Independent-Set is in P and the problem of checking a graph has a Hamiltonian Path is not in P.