Discussion between Ahmad and Yuval Filmus

Feeds

17:48

Q: How can I show that a problem is not $NP$

Consider the following image: The problem is, "can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up". Prove that this problem is $NP-hard$. I know that to prove that it is $NP-hard$, I must reduce a $NPC$ problem to it. However, I gu...

Yuval Filmus

Your problem is in NP. Given a placement of the small squares inside the large square, you can check its legality in polynomial time.

Ahmad

@Yuval oh! I thought that the answer just includes a yes and a series of rectangles.

@david right, I had a mistake in figuring out the given answer and also proving NP hard mislead me more. I wonder why they didn't ask if it's a NPC. Anyways, by the way, do you have a hint how can I show that it's NPC? Which problem can I reduce to it, and what is the above problem called in the literature (for search)

@YuvalFilmus, Could you guide me about the update of the answer?

Yuval Filmus

I think you should be able to solve it yourself. Unfortunately, the stackexchange platform isn't really suitable to this kind of discussion.

Ahmad

@YuvalFilmus I didn't ask for its solution! My question title is something else. I just asked which problems are considered non-NP. I tried to bring an example of a problem that can't be verified in polynomial time, unless I have a mistake in defining the certificate. Yet, the general question remains without considering the example.

@YuvalFilmus in the new case, the certificate includes the subset or the assortment too?!!

Yuval Filmus

The certificate can include any data you want, as long as it's polynomial size.

Ahmad

17:48

@YuvalFilmus Sorry, I am a bit confused. You mean that the certificate could only include the subset or their placement. I think in the former case, it wouldn't be polynomially verfiable, but in the latter case it is. So, are they two different problems? or the definition is that they must give as much as information in certifcate in polynomial size!

Yuval Filmus

The certificate can be whatever you want, as long as its size is polynomial in the size of the instance itself.

Ahmad

@YuvalFilmus Sorry, I know that I am very novice and here is not for this discussions! by whaterver you want you mean this is me who requests for more info?

Yuval Filmus

It just means whatever you want. I'm not sure how to express this in any other way.

Ahmad

Hi Yuval, but you didn't answer my last question. What is the difference if the certificate just shows the subset or also their placements? It's very important in verifying the answer not?

I also didn't get your emphasis on "You". You might mean that I must want the most possible information (in polynomial size). Otherwise, I may request little information, and it changes the problem!

David Richerby

18:16

The certificate can include any information that lets you verify that the instance is a "yes" instance. The only requirement is that the certificate has polynomial size and can be checked in polynomial time.

Different people might use different certificates: for any language, there are infinitely many possibilities for the certificates.

Designing certificates is like designing algorithms: it's a creative act and there isn't single correct answer. Often, there will be a "most natural" answer (e.g., for SAT, the "obvious" certificate would be a truth assignment to the variables) but that doesn't mean it's the only answer.

2 hours later…

Stella Biderman

19:59

I think the thing you're tripped up on is that you think there is some kind of precommitment to the shape of a certificate. You're not allowed to say "is this problem in NP if you can only provide a certificate that satisfies such and such rule." To be in NP there needs to be *some way to define a certificate*. As David said, this can be very hard and intuitive.

The easiest example of a hard certificate I know of is that if you don't know the AKS Theorem (which says that primality testing is in P) it is possible to nevertheless show that a number is prime in a certificate. However, the cer…

Try looking at the order of quantifiers for the definition of NP. A language, L, is in NP if and only if for every x in L there exists a certificate such that blah blah blah.

If there is *any* certificate the language is in NP. And the language and the certificate are defined totally independently - the language cannot reference the certificate.

next day → last day (16 days later) »

all rooms