Vertex enumeration problem
கணிதத்தில், ஒரு பாலிடோப், ஒரு பாலிஹெட்ரல் செல் காம்ப்ளக்ஸ், ஒரு ஹைப்பர்பிளேன் ஏற்பாடு அல்லது தனித்துவமான வடிவவியலின் வேறு ஏதேனும் பொருளுக்கான உச்சி கணக்கீட்டு சிக்கல், பொருளின் சில முறையான பிரதிநிதித்துவம் கொடுக்கப்பட்ட பொருளின் செங்குத்துகளை தீர்மானிக்கும் சிக்கலாகும். ஒரு செவ்வக உதாரணம் நேரியல் ஏற்றத்தாழ்வுகளின் தொகுப்பால் குறிப்பிடப்பட்ட ஒரு குவிந்த பாலிடோப்பின் செங்குத்துகளின் கணக்கீட்டின் சிக்கலாகும்ஃ இங்கு A என்பது ஒரு m × n மேட்ரிக்ஸ், x என்பது மாறிகளின் n × 1 நெடுவரிசை திசையன், மற்றும் b என்பது மாறிலிகளின் m × 1 நெடுவரிசை திசையன். செங்குத்துகள் கொடுக்கப்பட்ட எல்லை ஏற்றத்தாழ்வுகளைக் கண்டுபிடிப்பதற்கான தலைகீழ் (இரட்டை) சிக்கல் முகப்பு கணக்கீடு என்று அழைக்கப்படுகிறது (குவிந்த ஹல் வழிமுறைகளைப் பார்க்கவும்). கணக்கீட்டு சிக்கலானது சிக்கலின் கணக்கீட்டு சிக்கலானது கணினி அறிவியலில் ஆராய்ச்சிக்கு உட்பட்ட ஒரு விஷயமாகும். வரம்பற்ற பாலிஹெட்ராவைப் பொறுத்தவரை, சிக்கல் NP-கடினமானது என்று அறியப்படுகிறது, மேலும் துல்லியமாக, P = NP தவிர, ஒருங்கிணைந்த உள்ளீடு-வெளியீட்டு அளவில் பல்லுறுப்புக்கோவை நேரத்தில் இயங்கும் வழிமுறை எதுவும் இல்லை. டேவிட் அவிஸ் மற்றும் கோமே ஃபுகுடா ஆகியோரின் 1992 ஆம் ஆண்டு கட்டுரை ஒரு தலைகீழ்-தேடல் வழிமுறையை முன்வைக்கிறது, இது ஒரு பாலிடோப்பின் v செங்குத்துகளை d பரிமாணங்களில் உள்ள n ஏற்றத்தாழ்வுகளின் (அல்லது, இரட்டிப்பாக, d பரிமாணங்களில் உள்ள n புள்ளிகளின் குவிந்த மேலோட்டத்தின் v அம்சங்கள், ஒவ்வொரு அம்சமும் சரியாக d கொடுக்கப்பட்ட புள்ளிகளைக் கொண்டுள்ளது) O (ndv) மற்றும் இடைவெளி O (nd). d பரிமாணங்களில் n ஹைப்பர்பிளேன்களின் எளிய ஏற்பாட்டில் உள்ள v செங்குத்துகளை O (n2dv) நேரம் மற்றும் O (nd) விண்வெளி சிக்கலில் காணலாம். அவிஸ்-ஃபுகுடா வழிமுறையானது ஓரியண்டட் மேட்ராய்டுகளுக்கான கிறிஸ்-கிராஸ் வழிமுறைக்கு ஏற்றது. குறிப்புகள் குறிப்புகள் வடிவியல் வழிமுறைகள் நேரியல் நிரலாக்க பாலிஹெட்ரல் காம்பினடோரிக்ஸ் பாலிஹெட்ரா டிஸ்கிரீட் வடிவியல் கணித சிக்கல்கள் கணித வடிவியல்