Bissoy.com
Doctors Medicines MCQs Q&A

Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?

Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement? Correct Answer Q<sub>1</sub> is in NP, Q<sub>2</sub> is NP hard

Concept:

If a NP complete problem is reducible to another problem in polynomial time than that other problem becomes NP hard.

If X ϵ NP complete and X reduces to Y in polynomial time than Y is NP hard.

3 - SAT is NP complete problem

Explanation:

Q1 reduces in polynomial time to 3- SAT. As 3 - SAT is NP complete problem, Q1 is easier than NPC. So, Q1 can’t be NP hard. It is in NP.

3- SAT reduces in polynomial time to Q2. As, 3- SAT is NP complete so, Q2 will be NP hard.

Therefore, Q1 is NP and Q2 is NP hard.

Related Questions

The following are the conditions for selecting list of a suitable candidates to be called for interview after the written test for the recruitment is conducted/ organized for management-level persons of a multi-national company. For providing accounting services and sales the candidates must (a) be holding a graduation in basic science with 65% or above or B. E degree with 55% and above marks (b) have passed the written test with 70% or above marks (c) the age must be in the group 25 to 30 years as on 1/4/18 (d) have experience in an accounting firms for three years and diploma in accounting with 60% or above marks (e) be presently drawing CTC of 6 Lakhs per annum and above In case the applicant who satisfies all other terms above except 1) at (a) above, then be referred as Junior Accountant 2) at (d) & (e) above then be referred as Trainee-Accountant Satisfying all the above with experience of 5 years then be referred as senior-Accountant Satisfying all the above criteria (a-e) with CA/ ICWA / MBA (Finance) then be refereed as manager (Accounts) Read all the above information and answer the following question Shravani has passed H. SC with 72% of marks. She has done diploma in accountancy with 62% of marks. She was working with an organization in the field of accounting in the field of accounting from 4 years and was drawing CTC of 6.5 Lakhs presently. She is 28yrs as on July 2018. She may referred for the position of:
The following are the conditions for selecting list of a suitable candidates to be called for interview after the written test for the recruitment is conducted/organized for management - level persons for a multi - national company. For providing accounting services and sales the candidate must (a) be holding a graduation in basic science with 65% or above or B.E. degree with 55% and above marks (b) have passed the written test with 70% or above marks (c) the age must be in the group 25 to 30 years as on 1/4/18 (d) have experience in an accounting firms for three years and diploma in accounting with 60% or above marks (e)  be presently drawing CTC of 6 Lakhs per annum and above In case the applicant who satisfies all other terms above except 1) at (a) above, then be referred as Junior Accountant 2) at (d) & (e) above then be referred as Trainee - Accountant Satisfying all the above with experience of 5 years then the referred as senior-Accountant Satisfying all the above criteria (a - e) with CA/ICWA/MBA (Finance) then be referred as manager (Accounts) Read all the above information and answer the following question Praveen has done his Masters in physics. He has no experience in accounting neither diploma. He is ready to be on training for accounting after joining. For which position he may be referred
The following are the conditions for selecting a list of suitable candidates to be called for interview after the written test for the recruitment is conducted/ organized for management-level persons for a multi-national company. For providing accounting services and sales the candidate must (a) beholding graduation in basic science with 65% or above or B.E. degree with 55% and above marks (b) have passed the written test with 70% or above marks (c) the age must be in the group 25 to 30 years as on 1/4/18 (d) have experience in an accounting firm for three years and a diploma in accounting with 60% or above marks e) be presently drawing CTC 6 lakhs per annum and above In case the applicant who satisfies all other terms above except 1) at (a) above, then be referred to as Junior Accountant 2) at (d) & (e) above then be referred to as Trainee-Accountant Satisfying all the above with experience of 5 years then be referred to as senior-Accountant Satisfying all the above criteria (a-e) with CA/ICWA/MBA (Finance) then be referred to as manager (Accounts) Read all the above information and answer the following question   Praveen has done his Masters in physics. He has no experience in accounting neither diploma. He is ready to be on training for accounting after joining. For which position he may be referred.
The following are the conditions for selecting list of a suitable candidates to be called for interview after the written test for the recruitment is conducted/ organized for management-level persons of a multi-national company. For providing accounting services and sales the candidate must (a) be holding a graduation in basic science with 65% or above or B.E degree with 55% and above marks (b) have passed the written test with 70% or above marks (c) the age must be in the group 25 to 30 yrs as on 1/4/18 (d) have experience in an accounting firms for three yrs and diploma in accounting with 60% or above marks (e) be presently drawing CTC of 6 Lakhs per annum and above In case the applicant who satisfies all other terms above except 1) at (a) above, then be referred as Junior Accountant 2) at (d) & (e) above then be referred as Trainee-Accountant Satisfying all the above with experience of 5 yrs then be referred as senior-Accountant Satisfying all the above criteria (a-e) with CA/ ICWA/ MBA (Finance) then be refereed as manager (Accounts) Read all the above information and answer the following question: Radha Mohan has done her graduation in physics with 58% of marks. She has passed the written examination with 76% of marks. She is 27 yrs as on June 2018. She has the experience in the accounting company for four years with salary of 7 Lakhs per annum. She also has passed diploma in accounting with 61% of marks. She may be referred for the position of:
Imagine, you are solving a classification problems with highly imbalanced class. The majority class is observed 99% of times in the training data. Your model has 99% accuracy after taking the predictions on test data. Which of the following is true in such a case?
1. Accuracy metric is not a good idea for imbalanced class problems.
2.Accuracy metric is a good idea for imbalanced class problems.
3.Precision and recall metrics are good for imbalanced class problems.
4.Precision and recall metrics aren't good for imbalanced class problems.
Directions: Seven different boxes A, B, C, D, E, F and G of different colours viz., Orange, Pink, Purple, Yellow, Blue, Red and Green are arranged one above the other. The box at the bottom of arrangement is numbered 1, the above box is numbered 2 and so on. B is immediately above E. More than two boxes are above the Orange box. The Yellow box is immediately below A. Only one box is between the Orange box and F. G is immediately above the Red box. Only one box is between B and the Pink box. Only two boxes are between the Pink and the Green box. Only two boxes are between the Yellow box and the Orange box. The Purple box is neither at the top nor at the bottom of the arrangement.B is above Pink box. C is immediately above F. Neither C nor G is a Yellow box. G is not a Orange box. Question: Which combination represents the position of C and its colour?
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true? I. if L4 ∈ P, then L2 ∈ P II. if L1 ∈ P or L3 ∈ P, then L2 ∈ P III. L1 ∈ P, if and only if L3 ∈ P IV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P
The question given below consists of a statement, followed by three arguments numbered I, II and III. You have to decide which of the arguments is/are ‘strong’ arguments and which is/are ‘weak’ arguments and accordingly choose your answer from the alternatives given below each question. Statement: As part of an effort to address the rising cases of divorces in the country, China's Jiangsu province has introduced a voluntary 'divorce test' for couples planning to end their marriage. Couples who score above 60 may be able to save their marriage, the civil affairs bureau said. Around 34 lakh Chinese couples filed for divorce in 2017. Is this sort of a decision/ test legitimate? Arguments: I. Yes, it is a valid decision and will give couples a chance to save their relationship. II. No, if a couple has decided to end their relationship, such a test won’t be beneficial. III. Yes, there is no harm in giving the test, if they want to separate their ways they can. But there might be a ray of hope that they decide to rethink their decision.
Five boxes B1, B2, B3, B4 and B5 are placed one above the other in racks. The lowermost rack is numbered as one and just above the lowermost is numbered as two and so on. Each box is coloured with different colour such as L1, L2, L3, L4 and L5 (not necessarily in the same order). Two boxes are placed between L2 coloured box and L5 coloured box. Box B1 is not placed immediately above box B3. Box B4 is placed in the top most rack. L1 coloured box is placed immediate above L5 coloured box. Box B3 is coloured with L4. L5 coloured box is placed above L4 coloured box. Box B2 is coloured with L1. Which of the following boxes are placed immediately above and immediately below B5 box respectively?
There is a hint in this question and a statement is given later. Carefully read the excerpts provided and determine the statement based on that episode. The current Australian team has lost three of their last five Test series. They lost their last two Test series, one of which was against Pakistan, which is not considered to be a strong team now. Australia's two best batsman, Steve Smith and David Warner are currently suspended and their absence has weakened the Australian team. There is a lot of dissatisfaction and introspection about how their national team plays in Australia, how they show aggression on the field, how they do not show respect to the team against them, and neglecting the media at the most, and focusing only on winning only, the discussion on the future of the game is ongoing. There are. Australian cricket never reached such a low level. This is the best opportunity to knock them into their own house. In other words, if this India could not beat Australia in Australia in this series, then it would prove that the campaign around this team is only the same: the propaganda. Statement: India has a good chance of defeating Australia. Choose the right one from the next option A - The statement is completely true. B - statement is most true. There is no definitive definition based on C-statement. D-statement is completely false.