想了解一下实际工作中需要解决的 NP-complete 问题？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Engineering - 工程

想了解一下实际工作中需要解决的 NP-complete 问题？

想了解一下实际工作中需要解决的 NP-complete 问题？# Engineering - 工程

c*n2012-02-19 08:02

1 楼

the following code compiles fine under commandline
but it fails in eclipse, with error msg:
....having the same erasure ......
I checked the .class bytecode , it is exactly the same for the 2
methods (except for return and exception), caller code is able to pick
up the differences because javac actually did add annotation about the
generics parameter, so "erasure" is a lie!!!!!
import java.util.Map;
class ffff{
private static Integer fun(Map s) throws Exception {
return null;}
private static String fun(Map s){
return null;
}
}

h*x2012-02-19 08:02

2 楼

麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
决某 NP-complete 问题的吗？
如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
谢谢！

N*m2012-02-19 08:02

3 楼

MyEclipse没有任何问题

【在 c******n 的大作中提到】

: the following code compiles fine under commandline
: but it fails in eclipse, with error msg:
: ....having the same erasure ......
: I checked the .class bytecode , it is exactly the same for the 2
: methods (except for return and exception), caller code is able to pick
: up the differences because javac actually did add annotation about the
: generics parameter, so "erasure" is a lie!!!!!
: import java.util.Map;
: class ffff{
: private static Integer fun(Map s) throws Exception {

o*e2012-02-19 08:02

4 楼

帮你顶
不知道答案

【在 h**x 的大作中提到】

: 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
: 决某 NP-complete 问题的吗？
: 如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
: 谢谢！

F*n2012-02-19 08:02

5 楼

What will happen if I call
Map m = new HashMap();
fun(m);
How can it pick up the difference??

【在 c******n 的大作中提到】

C*r2012-02-19 08:02

6 楼

问得好~~~

s*n2012-02-19 08:02

7 楼

I read it somewhere but I can't be sure I remember it clearly.
Apparently, even before Generics, at java byte code level,
a class is allowed to have two methods of same signature,
if they have different return types.
class A // pseudo byte code
f(List)->String
f(List)->Integer
The byte code reference to a method actually includes the
return type, therefore the two methods can be distinguished.
// pseudo byte code invoking two methods
(A.f(List)->String) ();
(A.f(List)->Integer) ();
Of course, at java source level, we can't have such 2 methods.
That's only a compile time restriction. If you manually
create a class file with such methods, there's no problem with JVM.
With Generics, at source level,
class B
String f(List x);
Integer f(List x);
The two signatures can be distinguished at compile time, and
javac6 allows them; But only if they have different return types!
class C
void f(List x);
void f(List x);
C is illegal, because the compiled class file would
contain two methods that are identical at byte code level,
so javac6 doesn't allow C.
The language spec actually says nothing about return type.
Both B and C should be legal. Compilers should have no problem.
But C is impossible to be compiled into current byte code format.
Given the conflicting specs about java and byte code,
what should compilers do? Javac 5 disallowed B&C.
Java 6 allows B, not C. And Java 7 will disallow B&C again,
probably accompanied by amendment to spec.
Which is really a shame. It seems a perfectly legitimate need
to overload methods with different generic types.

F*n2012-02-19 08:02

8 楼

That's because you confuse Java language vs JVM byte code. They are not the
same by specification and JVM byte code can have a lot of illegal Java
constructs.
In fact today's best obfuscator utilizes this, for instance, directly write
a compiled byte code to replace Java names with weird illegal characters to prevent
decompiling.
Back to the question, I think LZ simply made a wrong observation during compiling. The class can be compiled but the caller will have problem if no Generic parameters are specified. He must have used javac to ONLY compile the class declaration file, so it appeared OK. But there is another file which contains caller, and Eclipse try to build them all and the problem shows.

【在 s******n 的大作中提到】

: I read it somewhere but I can't be sure I remember it clearly.
: Apparently, even before Generics, at java byte code level,
: a class is allowed to have two methods of same signature,
: if they have different return types.
: class A // pseudo byte code
: f(List)->String
: f(List)->Integer
: The byte code reference to a method actually includes the
: return type, therefore the two methods can be distinguished.
: // pseudo byte code invoking two methods