گزینه دو بنظرم صحیح هست ... این مساله شبیه همون مساله صحت پذیری یا ۳-SAT هست که اگه بهمون یک جواب نمونه رو بدن در زمان خطی میتونیم درست یا نادرست بودن اون رو متوجه بشیم . حالا اگه ساختمان داده یا همون رشته ای که ما رو از ریشه به یکی از برگ های درخت میرسونه رو نداشته باشیم عملا اینکار در زمان نمایی میتونه انجام بشه که اگه تو گزینه ها بود اون هم جواب درست مساله بود.