Impact factor for posts is a measurement of importance.

Impact factor for users reflect their authority, reputation and contribution on a particular topic.

Rating reflects the quality of posts.

Rating on Voofie is not a simple average of all ratings, but a weighted average of rating, weighted by the impact factor of users who rated.

Computational complexity theory

All

Article

Discussion

Q&A

Link

Submit
There's no community index, be the first to start one! Add community Index
4 items for Computational complexity theory
0
22
Rating:
This post has not been rated yet. Be the first to give a rating!
Impact:
This post has a impact factor of 22 and 957 pageviews

A simple proof of NP != P ?

It is well known that relativization cannot be used to prove or disprove NP not equal to P. This paper question this belief by giving a very simple prove of NP not equal to P using relativization.

ross_tang 15 Aug 10
0
11
Rating:
This post has not been rated yet. Be the first to give a rating!
Impact:
This post has a impact factor of 11 and 768 pageviews

Origami Crease Pattern Design Proved NP-Hard

Folding a square sheet of paper into an arbitrary 3D shape is proved to be NP-hard problem. It is proved by transforming the problem into circle packing problem[1].

[1] arxiv.org/abs/1008.1224: Circle Packing for Origami Design Is Hard

 


  ...

ross_tang 13 Aug 10
0
11
Rating:
This post has not been rated yet. Be the first to give a rating!
Impact:
This post has a impact factor of 11 and 483 pageviews

A HP Labs researcher claimed to have proved NP != P

Vinay Deolalikar, HP Labs researcher, claimed to have proved NP not equal to P. The website is his homepage in HP. You can find his 103 paper in pdf here. And he said he will post the final version when ready. Here is his email claiming to have solved the problem:

ross_tang 09 Aug 10
0
47
Rating:
This post has not been rated yet. Be the first to give a rating!
Impact:
This post has a impact factor of 47 and 802 pageviews

Calculation of Permanent with new method (with complexity the same as the Ryser's formula)

Permanent of a matrix is quite similar to that of determinant, though determinant can be found in polynomial time, while permanent is #P-complete (meaning that if you solve it, you can count the number of solution of all NP problem.)

In this paper, I am going to describe a new method to calculate permanent based on a very simple principle: ...

...
ross_tang 26 Jan 10
Related concepts
Selected Users
Avatar for ross_tang

ross_tang

Degree in Physics and Mathematics, Master in Physics
香港