Unary language
গণনামূলক জটিলতা তত্ত্বে, একটি ইউনারি ভাষা বা ট্যালি ভাষা হল একটি আনুষ্ঠানিক ভাষা (স্ট্রিংয়ের একটি সেট) যেখানে সমস্ত স্ট্রিংয়ের ফর্ম 1k থাকে, যেখানে "1" যে কোনও নির্দিষ্ট প্রতীক হতে পারে। উদাহরণস্বরূপ, {1,111,1111} ভাষাটি ইউনারি, যেমন ভাষাটি {1k। k হল মৌলিক}। এই ধরনের সমস্ত ভাষার জটিলতা শ্রেণীকে কখনও কখনও টালি বলা হয়। "ইউনারি" নামটি এসেছে এই সত্য থেকে যে একটি ইউনারি ভাষা হল ইউনারি সংখ্যা পদ্ধতিতে প্রাকৃতিক সংখ্যার একটি সেটের এনকোডিং। যেহেতু যে কোনও সীমাবদ্ধ বর্ণমালার উপর স্ট্রিংয়ের মহাবিশ্ব একটি গণনাযোগ্য সেট, তাই প্রতিটি ভাষাকে প্রাকৃতিক সংখ্যার একটি অনন্য সেট এ-তে ম্যাপ করা যেতে পারে; সুতরাং, প্রতিটি ভাষার একটি ইউনারি সংস্করণ {এ-তে 1k। k} রয়েছে। বিপরীতভাবে, প্রতিটি ইউনারি ভাষার একটি আরও সংক্ষিপ্ত বাইনারি সংস্করণ রয়েছে, প্রাকৃতিক সংখ্যা k-এর বাইনারি এনকোডিংয়ের সেট যাতে 1k ভাষায় থাকে। যেহেতু জটিলতা সাধারণত ইনপুট স্ট্রিংয়ের দৈর্ঘ্যের পরিপ্রেক্ষিতে পরিমাপ করা হয়, তাই একটি ভাষার ইউনারি সংস্করণ মূল ভাষার তুলনায় "সহজ" হতে পারে। উদাহরণস্বরূপ, যদি কোনও ভাষাকে ও (2এন) সময়ে শনাক্ত করা যায়, তবে তার ইউনারি সংস্করণটি ও (এন) সময়ে শনাক্ত করা যেতে পারে, কারণ এন সূচকীয়ভাবে বড় হয়ে গেছে। আরও সাধারণভাবে, যদি কোনও ভাষাকে ও (এফ (এন)) সময় এবং ও (জি (এন)) স্থানে শনাক্ত করা যায়, তবে তার ইউনারি সংস্করণটি ও (এন + এফ (লগ এন)) সময় এবং ও (জি (লগ এন)) স্থানে শনাক্ত করা যেতে পারে (কেবল ইনপুট স্ট্রিংটি পড়ার জন্য আমাদের ও (এন) সময় প্রয়োজন)। যাইহোক, যদি কোনও ভাষায় সদস্যপদ অনিবার্য হয়, তবে তার একক সংস্করণে সদস্যপদও অনিবার্য। অন্যান্য জটিলতা শ্রেণীর সাথে সম্পর্ক TALLY পি/পলিতে রয়েছে-এমন ভাষার শ্রেণী যা বহুপদী সময়ে স্বীকৃত হতে পারে একটি পরামর্শ ফাংশন দেওয়া যা শুধুমাত্র ইনপুট দৈর্ঘ্যের উপর নির্ভর করে। এই ক্ষেত্রে, প্রয়োজনীয় পরামর্শ ফাংশনটি খুব সহজ-এটি প্রতিটি ইনপুট দৈর্ঘ্য k-এর জন্য একটি একক বিট প্রদান করে যা 1k ভাষায় আছে কি না তা নির্দিষ্ট করে। একটি ইউনারি ভাষা অপরিহার্যভাবে একটি বিরল ভাষা, কারণ প্রতিটি এন-এর জন্য এটিতে দৈর্ঘ্য এন-এর সর্বাধিক একটি মান এবং দৈর্ঘ্যের সর্বাধিক এন-এর মান থাকে, তবে সমস্ত বিরল ভাষাগুলি ইউনারি নয়; সুতরাং টালি স্পার্সে রয়েছে। এটি বিশ্বাস করা হয় যে কোনও এনপি-হার্ড ইউনারি ভাষা নেইঃ যদি এমন কোনও ইউনারি ভাষা থাকে যা এনপি-সম্পূর্ণ, তবে পি = এনপি। এই ফলাফলটি বিরল ভাষায় প্রসারিত করা যেতে পারে। যদি এল একটি ইউনারি ভাষা হয়, তাহলে এল * (এল-এর ক্লেইন তারকা) একটি নিয়মিত ভাষা। ট্যালি শ্রেণী জটিলতা শ্রেণী পি1 হল ইউনারি ভাষার শ্রেণী যা একটি বহুপদী সময় টুরিং মেশিন দ্বারা স্বীকৃত হতে পারে (এর ইনপুট ইউনারিতে লেখা); এটি পি শ্রেণীর এনালগ। ইউনারি সেটিংয়ে এনপি-র এনালগ হল এনপি1। একটি গণনা শ্রেণী #P 1, যা #P এর এনালগ, তাও জানা যায়। রেফারেন্স নোটস জেনারেল রেফারেন্স ল্যান্স ফোর্টনো। প্রিয় উপপাদ্যঃ ছোট সেট। এপ্রিল 18,2006। http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html আনুষ্ঠানিক ভাষা গণনামূলক জটিলতা তত্ত্ব